Exact majority C-colourings of balanced Hamming graphs and grids

Abstract

A majority C-colouring partitions a graph into classes in which every vertex has at least half of its neighbours. Write $M(G)$ for the maximum number of classes. We determine $M(K_q^{\square(2k+1)})=\left\lfloor\frac{q^{k+1}}{\lfloor q/2\rfloor+1}\right\rfloor\qquad(q\ge3,\ k\ge0).$ The lower bound follows from explicit rectangular partitions and a uniform three-dimensional bridge. A punctured-rectangle construction supplies both the bridge and a partition in the intermediate dimension. The upper bound is a classical consequence of Hamming edge isoperimetry; an elementary proof is included. We also prove $M(C_m\square P_n)=\frac n2\lfloor m/2\rfloor$ for $m\ge4$ and even $n\ge2$, contradicting the cylinder assertion of Conjecture 4 in arXiv:2608.27669v1 for odd $m\ge7$ and even $n\ge6$. Further layer bounds determine additional cylinder and torus families.