Majority coloring games solved for trees cycles and subdivisions
Structural and computational aspects of majority coloring games
Discrete Mathematics
Summary
This paper studies a game where two players color the dots (vertices) on a network (graph) so that no dot shares a color with more than half its neighbors. The authors identify cases where three colors always let the first player win, such as certain trees and graphs made by dividing edges. They also find the exact number of colors needed for cycles and show that deciding these colorings in some settings is computationally very hard. Their work advances understanding of how such coloring games behave on different graph shapes.
What this means in practice
- •For network designers: Use majority coloring game results to ensure fair resource allocation in hierarchical network topologies modeled as trees and subdivisions.
- •For algorithm developers: Leverage complexity results on strong majority coloring to identify and avoid computationally difficult cases in graph coloring algorithm design.
A theory result. No direct application yet.
Authors
Yash Chawda, Saraswati Girish Nanoti, Brahadeesh Sankarnarayanan, Eshwar Srinivasan
Abstract
A majority coloring of a graph $G = (V,E)$ is a coloring of $V(G)$ such that, for each vertex $v$, the number of neighbors of $v$ with the same color as $v$ is at most $deg(v)/2$. A strong majority coloring is a coloring of $V(G)$ such that, for each vertex $v$, every monochromatic subset of $N(v)$ has size at most $deg(v)/2$. The (strong) majority coloring game is a two-player Maker-Breaker-type game, in which two players Alice and Bob color the vertices of a graph $G$ alternately, maintaining the (strong) majority condition. The least number of colors such that Alice has a winning strategy in such a game is called the (strong) majority game chromatic number of the graph $G$, denoted $μ_g(G)$ (or $\mathrm{Maj}_g(G)$ for the strong version). For the majority coloring game, we prove that $μ_g(G) \le 3$ under the following cases: $G$ is a $2$-caterpillar, $G$ is a rooted tree with all leaves at depth $k \le 4$, and $G$ is a subdivision of some graph. The latter resolves a problem posed by Bosek--Grytczuk--Jakóbczak in 2019, who also asked whether $μ_g(T) \le 3$ for every tree $T$. For the latter question, we discuss various difficulties that arise when natural strategies are attempted by Alice to win the majority coloring game on trees. We include a comparison with the marking game and relaxed coloring game on trees, and with the majority coloring game on locally finite acyclic graphs $G$ with $δ(G) > 1$. For the strong majority coloring game, we compute $\mathrm{Maj}_g(C_n)$ exactly for each cycle $C_n$, $n \ge 3$. We also initiate the study of the computational complexity of the strong majority coloring game; specifically, we prove that the decision version of the Strong Majority Game Chromatic Number problem is PSPACE-complete. We also show that the Strong Majority 2-Coloring problem is NP-complete on Eulerian graphs.