Metraipolis › archive › dc_afdcde35129f

On the majority game chromatic number of forests and other graphs — arXiv:2609.23803

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.23803
License (as archived): CC0-1.0
Archived: 2026-10-09T21:44:54.307Z
SHA-256 of the archived text: a008e41de5cbddd6f5118a24fc2b5fa3b688d998772bec6669af8f7324177d95
Stable URL of this page: https://metraipolis.com/documento/dc_afdcde35129f

How to cite

On the majority game chromatic number of forests and other graphs — arXiv:2609.23803 — arXiv (en), https://arxiv.org/abs/2609.23803 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_afdcde35129f (Metraipolis archive dc_afdcde35129f, sha256 a008e41de5cbddd6f5118a24fc2b5fa3b688d998772bec6669af8f7324177d95)

BibTeX

@misc{dcafdcde35129f,
  title = {On the majority game chromatic number of forests and other graphs — arXiv:2609.23803},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.23803},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_afdcde35129f; sha256 a008e41de5cbddd6f5118a24fc2b5fa3b688d998772bec6669af8f7324177d95},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.23803. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

A majority coloring 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 et al. (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 col_g(G)$, where $col_g(G)$ is the game coloring number of $G$. It is known (cf. Faigle et al. (1993)) that, for any acyclic graph $G$, $col_g(G) \leq 4$, so $\mu_g(G) \leq 4$ as well. We improve this bound by showing that $\mu_g(G) \leq 3$ for any acyclic graph $G$ of maximum degree at most $4$. We also show that $\mu_g(G) = 2$ if $G$ is a nonempty path, star, or complete graph, or a disjoint union of such graphs. These improve the results of Bosek et al. We also initiate the study of the computational complexity of the pre-coloring extension problem for the static and game versions of majority coloring. We show that the Majority $k$-precoloring Extension problem is NP-complete for each $k \geq 2$. When $k = 2$, it remains NP-complete on the class of bipartite graphs where maximum degrees of each part are $5$ and $6$, and when $k = 3$ it remains NP-complete on the class of $12$-regular planar graphs. We show that the game version is PSPACE-complete, even when the number of colors $k=\chi(G)$, and even when $k=2$ and $G$ is a bipartite graph in which one part has maximum degree equal to $9$. The results on the game versions also hold for the variation where Bob starts the game.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-22 in math.CO).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2609.23803 — 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-09T21:26:41.135Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).