Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 34 min ago
PreprintarXiv licencearXiv

The game chromatic number of generalized Mycielski graphs of paths and cycles

  • Yushuang Mou
  • Qiang Sun
  • Chao Zhang
Open at sourcePDFDOICite

Abstract

The graph coloring game is a two-player game in which the players alternately color an uncolored vertex of a graph G. The game chromatic number is the minimum number of colors needed for the first player to guarantee a win. We investigate this parameter for generalized Mycielski graphs Mk(G), where G is a path Pn or a cycle Cn with n vertices. For every k≥2 and n≥5, we establish 4≤χg(Mk(Pn))≤5 and 4≤χg(Mk(Cn))≤5. We also determine the exact values χg(M2(P5))=χg(M2(P6))=4. The proofs of the lower bounds use a configuration in which Bob can create two threats simultaneously, while the four-color upper bounds in the two exact cases are proved using the double-doctor lemma. Thus the number of layers and the order of the base graph may grow, but the game chromatic number remains bounded by five.

Related

  1. Generalized Chromatic Polynomials of Cycles and uni-cyclic Graphs
    Dipnit Biswas, R. Venkatesh
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. On the exact quantum chromatic number of generalized Johnson graphs
    Gaojun Luo, Xiwang Cao, Shitao Li +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Complete characterization of disconnected one-point unions of cycles with local antimagic chromatic number 2
    Gee-Choon Lau, Wai Chee Shiu
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. On the k-Distance Chromatic Number of Unicyclic Graphs
    Rosário Fernandes, Rúben Palma
    Discrete Mathematics LettersPeer-reviewedCC BYFull textGeneral mathematicsDOAJ
  5. Minimal Cayley graphs with large chromatic number
    James Davies, Meike Hatzel, Liana Yepremyan
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{mou2026game,
  title = {{The game chromatic number of generalized Mycielski graphs of paths and cycles}},
  author = {Yushuang Mou and Qiang Sun and Chao Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.02283},
  eprint = {2609.02283},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.02283},
}
RIS
TY  - UNPB
TI  - The game chromatic number of generalized Mycielski graphs of paths and cycles
AU  - Yushuang Mou
AU  - Qiang Sun
AU  - Chao Zhang
PY  - 2026
DA  - 2026/09/02
PB  - arXiv
DO  - 10.48550/arxiv.2609.02283
UR  - https://arxiv.org/abs/2609.02283
AB  - The graph coloring game is a two-player game in which the players alternately color an uncolored vertex of a graph G. The game chromatic number is the minimum number of colors needed for the first player to guarantee a win. We investigate this parameter for generalized Mycielski graphs M_k(G), where G is a path P_n or a cycle C_n with n vertices. For every k≥2 and n≥5, we establish 4≤χ_g(M_k(P_n))≤5 and 4≤χ_g(M_k(C_n))≤5. We also determine the exact values χ_g(M_2(P_5))=χ_g(M_2(P_6))=4. The proofs of the lower bounds use a configuration in which Bob can create two threats simultaneously, while the four-color upper bounds in the two exact cases are proved using the double-doctor lemma. Thus the number of layers and the order of the base graph may grow, but the game chromatic number remains bounded by five.
ER  -