{"id":"arxiv/2609.31674","url":"https://arxiv.org/abs/2609.31674","tags":["math.CO"],"score":0,"title":"Exact majority C-colourings of balanced Hamming graphs and grids","domain":"math.CO","source":"arxiv","authors":["ZeHua Lu"],"reviews":0,"subject":"math.CO","summary":"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.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-16","reactions":{}}