Metraipolis › archive › dc_4655803813bb
Structural and computational aspects of majority coloring games — arXiv:2609.37796
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.37796
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T18:33:45.083Z
- SHA-256 of the archived text
475c66e4e434e796995e31216240629fc73c210bc80ee6f91105a58f49e8f130- Stable URL of this page
https://metraipolis.com/documento/dc_4655803813bb
How to cite
Structural and computational aspects of majority coloring games — arXiv:2609.37796 — arXiv (en), https://arxiv.org/abs/2609.37796 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4655803813bb (Metraipolis archive dc_4655803813bb, sha256 475c66e4e434e796995e31216240629fc73c210bc80ee6f91105a58f49e8f130)
BibTeX
@misc{dc4655803813bb,
title = {Structural and computational aspects of majority coloring games — arXiv:2609.37796},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.37796},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4655803813bb; sha256 475c66e4e434e796995e31216240629fc73c210bc80ee6f91105a58f49e8f130},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.37796. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\mu_g(G)$ (or $\mathrm{Maj}_g(G)$ for the strong version). For the majority coloring game, we prove that $\mu_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 $\mu_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 $\delta(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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-30 in math.CO).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2609.37796 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T17:59:19.237Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).