On the majority game chromatic number of forests and other graphs
Abstract
A majority coloring of a graph G is a vertex coloring of G in which no vertex has more than half of its neighbors colored with its own color. The least number of colors required for a majority coloring of G is the majority chromatic number μ(G). The majority coloring game, introduced by Bosek et al. (2019), is a two-player Maker-Breaker-type game where the players alternately color vertices while maintaining the majority condition at each vertex; the least number of colors required for the first player to have a winning strategy on G is the majority game chromatic number μg(G). In contrast with the static case, Bosek et al. show that μg(G) is unbounded in general, while μg(G)≤ colg(G), where colg(G) is the game coloring number of G. It is known (cf. Faigle et al. (1993)) that, for any acyclic graph G, colg(G) ≤ 4, so μg(G) ≤ 4 as well. We improve this bound by showing that μg(G) ≤ 3 for any acyclic graph G of maximum degree at most $4$. We also show that μg(G) = 2 if G is a nonempty path, star, or complete graph, or a disjoint union of such graphs. These improve the results of Bosek et al. We also initiate the study of the computational complexity of the pre-coloring extension problem for the static and game versions of majority coloring. We show that the Majority k-precoloring Extension problem is NP-complete for each k ≥ 2. When k = 2, it remains NP-complete on the class of bipartite graphs where maximum degrees of each part are $5$ and $6$, and when k = 3 it remains NP-complete on the class of $12$-regular planar graphs. We show that the game version is PSPACE-complete, even when the number of colors k=χ(G), and even when k=2 and G is a bipartite graph in which one part has maximum degree equal to $9$. The results on the game versions also hold for the variation where Bob starts the game.
Related
BibTeX
@misc{chawda2026majority,
title = {{On the majority game chromatic number of forests and other graphs}},
author = {Yash Chawda and Saraswati Girish Nanoti and Brahadeesh Sankarnarayanan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.23803},
eprint = {2609.23803},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23803},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the majority game chromatic number of forests and other graphs
AU - Yash Chawda
AU - Saraswati Girish Nanoti
AU - Brahadeesh Sankarnarayanan
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2609.23803
UR - https://arxiv.org/abs/2609.23803
AB - A majority coloring of a graph G is a vertex coloring of G in which no vertex has more than half of its neighbors colored with its own color. The least number of colors required for a majority coloring of G is the majority chromatic number μ(G). The majority coloring game, introduced by Bosek et al. (2019), is a two-player Maker-Breaker-type game where the players alternately color vertices while maintaining the majority condition at each vertex; the least number of colors required for the first player to have a winning strategy on G is the majority game chromatic number μ_g(G). In contrast with the static case, Bosek et al. show that μ_g(G) is unbounded in general, while μ_g(G)≤ col_g(G), where col_g(G) is the game coloring number of G. It is known (cf. Faigle et al. (1993)) that, for any acyclic graph G, col_g(G) ≤ 4, so μ_g(G) ≤ 4 as well. We improve this bound by showing that μ_g(G) ≤ 3 for any acyclic graph G of maximum degree at most $4$. We also show that μ_g(G) = 2 if G is a nonempty path, star, or complete graph, or a disjoint union of such graphs. These improve the results of Bosek et al. We also initiate the study of the computational complexity of the pre-coloring extension problem for the static and game versions of majority coloring. We show that the Majority k-precoloring Extension problem is NP-complete for each k ≥ 2. When k = 2, it remains NP-complete on the class of bipartite graphs where maximum degrees of each part are $5$ and $6$, and when k = 3 it remains NP-complete on the class of $12$-regular planar graphs. We show that the game version is PSPACE-complete, even when the number of colors k=χ(G), and even when k=2 and G is a bipartite graph in which one part has maximum degree equal to $9$. The results on the game versions also hold for the variation where Bob starts the game.
ER -