Ze-Hua Lu

Exact majority C-colourings of balanced Hamming graphs and grids

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 explici...