On the majority game chromatic number of forests and other graphs

A majority coloring (also called an unfriendly partition) 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 $\mu (G)$. The majority coloring game, introduced by Bosek--Grytczuk--Jak\'obczak (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 ${\mu }_g(G)$. In contrast with the static case, Bosek et al. show that ${\mu }_g(G)$ is unbounded in general, while ${\mu }_g(G)\le co{l}_g(G)$, where $co{l}_g(G)$ is the game coloring number of $G$. It is known that for any acyclic graph $G$, $co{l}_g(G)\le 4$, and hence ${\mu }_g(G)\le 4$. We improve this bound by showing that ${\mu }_g(G)\le 3$ for any acyclic graph $G$ of maximum degree at most $4$. We also show that ${\mu }_g(G)\le 2$ if $G$ is a path, a star, or a complete graph, improving results of Bosek et al. We also initiate the study of the computational complexity of the majority coloring game. We show that the pre-coloring extension problem for majority coloring on $G$ with a palette of $\chi (G)$ colors is NP-complete, and that its game version is PSPACE-complete. Furthermore, the problem remains NP-complete, and its game version remains PSPACE-complete, even with a palette of $2$ colors.