Skip to content
DraconiticResearch
Search Sources API
201,818 studies31 sourcesUpdated 51 min ago
PreprintarXiv licencearXiv

Connected Coloring Games on Corona Products of Graphs

  • Daša Mesarič Štesl
Open at sourcePDFDOICite

Abstract

We study the connected coloring game on corona products of graphs. For connected graphs G and H, we prove the sharp upper bound χcg(G∘ H)≤max{Δ(G),Δ(H)+1}+1 and establish a further bound using the Bob-start ordinary coloring game on the second factor. We show that the difference between the Alice-start and Bob-start connected game chromatic numbers can be arbitrarily large in either direction. We further prove that a connected subgraph may have arbitrarily larger connected game chromatic number than its ambient connected graph, and that χcg(G∘ H) cannot be bounded in terms of χcg(G) and χcg(H) alone, even when both factors have connected game chromatic number $2$. We also obtain corona products for which the difference χg−χcg is arbitrarily large and construct infinitely many connected graphs with χg<χcg. Finally, for corona products of trees, we prove the universal upper bound $5$, characterize those attaining the value $3$, give structural sufficient conditions for the value $4$, and exhibit a broad family attaining the value $5$.

Related

  1. Covering Families for DP-Coloring of Cartesian Products with Complete Bipartite Graphs
    Hemanshu Kaul, Jeffrey A. Mudrock, Emily A. Psyhogios +3
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Structural and computational aspects of majority coloring games
    Yash Chawda, Saraswati Girish Nanoti, Brahadeesh Sankarnarayanan +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Bounds for B-coloring planar and outerplanar graphs
    Ryan Martin, Miklós Ruszinkó, Gábor Sárközy
    Discrete MathematicsPeer-reviewedLicence not statedCombinatorics & discrete mathematicsHAL
  4. COLORING SEMIMINIMAL CAYLEY GRAPHS
    Ignacio Garc Ía-Marco, Kolja Knauer, Giuliamaria Menara
    HALPreprintCC BY 4.0Full textGeneral mathematicsHAL
  5. Double-Partition Coloring problem: a unified approach for conflict-free coloring of hypergraphs and other coloring problems in graphs
    Mauro Lucci, Graciela Nasini, Paola Tolomei +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{stesl2026connected,
  title = {{Connected Coloring Games on Corona Products of Graphs}},
  author = {Daša Mesarič Štesl},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.29650},
  eprint = {2610.29650},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.29650},
}
RIS
TY  - UNPB
TI  - Connected Coloring Games on Corona Products of Graphs
AU  - Daša Mesarič Štesl
PY  - 2026
DA  - 2026/10/21
PB  - arXiv
DO  - 10.48550/arxiv.2610.29650
UR  - https://arxiv.org/abs/2610.29650
AB  - We study the connected coloring game on corona products of graphs. For connected graphs G and H, we prove the sharp upper bound χ_cg(G∘ H)≤max{Δ(G),Δ(H)+1}+1 and establish a further bound using the Bob-start ordinary coloring game on the second factor. We show that the difference between the Alice-start and Bob-start connected game chromatic numbers can be arbitrarily large in either direction. We further prove that a connected subgraph may have arbitrarily larger connected game chromatic number than its ambient connected graph, and that χ_cg(G∘ H) cannot be bounded in terms of χ_cg(G) and χ_cg(H) alone, even when both factors have connected game chromatic number $2$. We also obtain corona products for which the difference χ_g−χ_cg is arbitrarily large and construct infinitely many connected graphs with χ_g<χ_cg. Finally, for corona products of trees, we prove the universal upper bound $5$, characterize those attaining the value $3$, give structural sufficient conditions for the value $4$, and exhibit a broad family attaining the value $5$.
ER  -