Majority game coloring uses fewer colors on forests and simple graphs
On the majority game chromatic number of forests and other graphs
Discrete Mathematics
Summary
This paper studies a coloring game played on networks where players take turns coloring points so that no point has more than half of its neighbors sharing its color. The authors show that for tree-like graphs and some simple graph types fewer colors are needed than previously known. The paper also finds that deciding if a partial coloring can be extended is computationally hard. These results improve understanding of how complexity and color requirements vary in such coloring games.
What this means in practice
- •For graph algorithm designers: Understand tighter upper bounds on colors needed for majority coloring games on forests and low-degree graphs to optimize coloring algorithms.
- •For complexity theorists: Use NP- and PSPACE-completeness results for majority coloring extension problems as benchmarks in computational complexity studies.
A theory result. No direct application yet.
Authors
Yash Chawda, Saraswati Girish Nanoti, Brahadeesh Sankarnarayanan
Abstract
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 $μ(G)$. The majority coloring game, introduced by Bosek--Grytczuk--Jakóbczak (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) \le \mathrm{col}_g(G)$, where $\mathrm{col}_g(G)$ is the game coloring number of $G$. It is known that for any acyclic graph $G$, $\mathrm{col}_g(G) \le 4$, and hence $μ_g(G) \le 4$. We improve this bound by showing that $μ_g(G) \le 3$ for any acyclic graph $G$ of maximum degree at most $4$. We also show that $μ_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 $χ(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.