{"id":"arxiv/2608.27669","url":"https://arxiv.org/abs/2608.27669","tags":["math.CO"],"score":0,"title":"Majority C-coloring in Cartesian products","domain":"math.CO","source":"arxiv","authors":["Csilla Bujtás","Magda Dettlaff","Hanna Furmańczyk","Aleksandra Laskowska","Zsolt Tuza"],"reviews":0,"subject":"math.CO","summary":"A majority C-coloring of a graph $G$ assigns colors to the vertices such that every vertex shares its color with at least half of its neighbors. The maximum number of colors that can be used in such a coloring of $G$ is denoted by $\\overlineχ_{\\geqslant}(G)$. In this paper, the focus is on the majority C-coloring in Cartesian product graphs. It is shown that $\\overlineχ_{\\geqslant}(G \\square H) \\ge \\overlineχ_{\\geqslant}(G) \\overlineχ_{\\geqslant}(H)$ gives a sharp lower bound, but the difference also can be arbitrarily large. For two-dimensional Hamming graphs, the exact value…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-27","reactions":{}}