Structural and computational aspects of majority coloring games
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 Majg(G) for the strong version). For the majority coloring game, we prove that μg(G) ≤ 3 under the following cases: G is a $2$-caterpillar, G is a rooted tree with all leaves at depth k ≤ 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) ≤ 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 Majg(Cn) exactly for each cycle Cn, n ≥ 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.
Related
- Fractional majority coloring of digraphs: bounds and inapproximability
- Majority C-coloring in Cartesian products
- Connected Coloring Games on Corona Products of Graphs
- Computational complexity of the H-coloring problem in cubic graphs
- The Computational Complexity of the Ungar Games on Distributive Lattices
BibTeX
@misc{chawda2026structural,
title = {{Structural and computational aspects of majority coloring games}},
author = {Yash Chawda and Saraswati Girish Nanoti and Brahadeesh Sankarnarayanan and Eshwar Srinivasan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37796},
eprint = {2609.37796},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37796},
}
RIS
TY - UNPB
TI - Structural and computational aspects of majority coloring games
AU - Yash Chawda
AU - Saraswati Girish Nanoti
AU - Brahadeesh Sankarnarayanan
AU - Eshwar Srinivasan
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.37796
UR - https://arxiv.org/abs/2609.37796
AB - 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 Maj_g(G) for the strong version). For the majority coloring game, we prove that μ_g(G) ≤ 3 under the following cases: G is a $2$-caterpillar, G is a rooted tree with all leaves at depth k ≤ 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) ≤ 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 Maj_g(C_n) exactly for each cycle C_n, n ≥ 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.
ER -