The domatic number problem*

NEW

Problem: Reconstructed conjecture: for each fixed $r\ge1$, all but finitely many $r$-dimensional rectangular grid graphs

$$P_{n_1}\square P_{n_2}\square\cdots\square P_{n_r}\qquad(n_i\ge2)$$

are domatically full, i.e. have domatic number $d(G)=\delta(G)+1$. This is the standard meaning of an $r$-dimensional grid in this context. A domatic partition is a partition of $V(G)$ into dominating sets.

Result: The conjecture is false under this standard interpretation. For every $n\ge2$,

$$G_n=P_2\square P_2\square P_2\square P_n$$

is a $4$-dimensional grid with $\delta(G_n)=4$, but $d(G_n)<5=\delta(G_n)+1$. Hence there are infinitely many non-domatically-full $4$-dimensional grids.

Proof. Write $Q_3=P_2\square P_2\square P_2$, with vertices $\{0,1\}^3$, and view $G_n$ as $n$ layers $Q_3\times\{1,\dots,n\}$. Suppose, for contradiction, that $G_n$ has a $5$-domatic coloring. Then every closed neighborhood must contain all five colors.

Consider the endpoint layer $Q_3\times\{1\}$. For $x\in Q_3$,

$$N_{G_n}[(x,1)]=B(x)\times\{1\}\cup\{(x,2)\},$$

where $B(x)=N_{Q_3}[x]$ has four vertices. Since this closed neighborhood has exactly five vertices, its five colors must be pairwise distinct.

Let $\alpha(x)$ be the color of $(x,1)$. Then every $B(x)$ is rainbow under $\alpha$. In $Q_3$, any two vertices at Hamming distance $1$ or $2$ lie together in some closed neighborhood $B(x)$, so equal-colored vertices in layer $1$ must be antipodal. Thus every color appears in layer $1$ at most twice.

There are eight vertices and five colors, so the color multiplicities in layer $1$ are either

$$(2,2,2,2,0)\quad\text{or}\quad(2,2,2,1,1).$$

Case 1: $(2,2,2,2,0)$. The four used colors occupy four antipodal pairs. Every $B(x)$ contains exactly one vertex from each antipodal pair, so every $B(x)$ has the same four colors. Therefore every vertex $(x,2)$ must have the one missing color. Thus layer $2$ is monochromatic. But then any vertex in layer $2$ sees at most three colors: the layer-$2$ color, its vertical neighbor in layer $1$, and possibly its vertical neighbor in layer $3$. This cannot be a $5$-domatic coloring.

Case 2: $(2,2,2,1,1)$. The three double colors occupy three antipodal pairs, and the two singleton colors occupy the remaining antipodal pair, say $p,\bar p$, with colors $s,t$. Each $B(x)$ contains exactly one vertex from each antipodal pair. Hence $B(x)$ contains exactly one of $s,t$, so $(x,2)$ must receive the other one. In particular, all vertices of $B(p)\times\{2\}$ have color $t$. Now the closed neighborhood of $(p,2)$ contains only color $t$ inside layer $2$, color $s$ from $(p,1)$, and at most one further color from $(p,3)$. Thus it contains at most three colors, contradiction.

Therefore no $G_n$ admits a $5$-domatic coloring. Since $\delta(G_n)=4$, $G_n$ is not domatically full. The family $\{P_2\square P_2\square P_2\square P_n:n\ge2\}$ gives infinitely many exceptions in dimension $4$, disproving the conjecture.

Citation: No external citation used; the counterexample and proof are given above.