Majority C-coloring in Cartesian products
Abstract
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 χ̅geqslant(G). In this paper, the focus is on the majority C-coloring in Cartesian product graphs. It is shown that χ̅geqslant(G □ H) ≥ χ̅geqslant(G) χ̅geqslant(H) gives a sharp lower bound, but the difference also can be arbitrarily large. For two-dimensional Hamming graphs, the exact value χ̅geqslant(Km □ Kn) = min{m,n} is established. Balanced Hamming graphs of higher dimension, that is the kth powers of complete graphs with respect to the Cartesian product, are also studied. It is proved that χ̅geqslant(Kn□, k)= nk/2 holds for every even integer k. If k is odd and the Hamming graph is the k-dimensional hypercube, then χ̅geqslant(K2□, k)= 2⌊ k/2⌋. On the other hand, a majority C-coloring of Kn□, k with at least $3 n^{\lfloor k/2\rfloor}/2 $ colors is presented for every n ≥ 7 and odd k ≥ 3. For Cartesian grids, the main result shows that χ̅geqslant(Pm □ Pn) = 1 + ⌊ m/2⌋ ⌊ n/2⌋ if at least one of m and n is odd, while χ̅geqslant(Pm □ Pn)=mn/4 holds if both parameters are even and m ≥ n ≥ 4. The paper concludes with a conjecture and several open problems.
Related
- Covering Families for DP-Coloring of Cartesian Products with Complete Bipartite Graphs
- Fractional majority coloring of digraphs: bounds and inapproximability
- Structural and computational aspects of majority coloring games
- On k-limited domination: complexity and Cartesian products
- Sn-equivariant L-classes of Cartesian powers of Witt spaces and the Hodge index conjecture for symmetric products
BibTeX
@misc{bujtas2026majority,
title = {{Majority C-coloring in Cartesian products}},
author = {Csilla Bujtás and Magda Dettlaff and Hanna Furmańczyk and Aleksandra Laskowska and Zsolt Tuza},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.27669},
eprint = {2608.27669},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.27669},
note = {CC0},
}
RIS
TY - UNPB
TI - Majority C-coloring in Cartesian products
AU - Csilla Bujtás
AU - Magda Dettlaff
AU - Hanna Furmańczyk
AU - Aleksandra Laskowska
AU - Zsolt Tuza
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2608.27669
UR - https://arxiv.org/abs/2608.27669
AB - 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 χ̅_geqslant(G). In this paper, the focus is on the majority C-coloring in Cartesian product graphs. It is shown that χ̅_geqslant(G □ H) ≥ χ̅_geqslant(G) χ̅_geqslant(H) gives a sharp lower bound, but the difference also can be arbitrarily large. For two-dimensional Hamming graphs, the exact value χ̅_geqslant(K_m □ K_n) = min{m,n} is established. Balanced Hamming graphs of higher dimension, that is the kth powers of complete graphs with respect to the Cartesian product, are also studied. It is proved that χ̅_geqslant(K_n^□, k)= n^k/2 holds for every even integer k. If k is odd and the Hamming graph is the k-dimensional hypercube, then χ̅_geqslant(K_2^□, k)= 2^⌊ k/2⌋. On the other hand, a majority C-coloring of K_n^□, k with at least $3 n^{\lfloor k/2\rfloor}/2 $ colors is presented for every n ≥ 7 and odd k ≥ 3. For Cartesian grids, the main result shows that χ̅_geqslant(P_m □ P_n) = 1 + ⌊ m/2⌋ ⌊ n/2⌋ if at least one of m and n is odd, while χ̅_geqslant(P_m □ P_n)=mn/4 holds if both parameters are even and m ≥ n ≥ 4. The paper concludes with a conjecture and several open problems.
ER -