Monotone classes of bounded game chromatic number have bounded arboricity

In the coloring game on a finite graph, Alice and Bob alternately color uncolored vertices with one of $k$ colors so that adjacent vertices get different colors. Alice moves first and wins if every vertex gets colored; Bob wins if some uncolored vertex sees all $k$ colors among its neighbors. The game chromatic number of a graph is the least $k$ for which Alice can force a win. We prove that for every $K$ there is $d$ such that every graph of average degree at least $d$ has a subgraph on which Bob wins the $k$-color game for every $k\le K$. Consequently, if a class of graphs is closed under taking subgraphs and its game chromatic numbers are bounded, then the edges of each of its graphs can be partitioned into a bounded number of forests, that is, the class has bounded arboricity. This answers Zhu's Question 3 (1999) in the affirmative. The proof combines the theorem of Kühn and Osthus that every graph of large enough average degree contains a subgraph of large average degree with no 4-cycle, with a strategy for Bob that adapts the weighting argument behind Beck's criterion for positional games: Bob uses weights to keep some uncolored vertex that can still be blocked from every color. The rest of the proof is checked in Lean, with the theorem of Kühn and Osthus as an explicit hypothesis. This work has not yet been reviewed by experts. The proofs, the Lean formalization and the text were produced by AI models (from OpenAI and Anthropic), working under the author's direction. Written proof, with Lean and computer checks; not yet reviewed by experts. Produced by AI models under the author's direction.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-19
DOI
https://doi.org/10.5281/zenodo.24376623
Primary Topic
Limits and Structures in Graph Theory
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Monotone classes of bounded game chromatic number have bounded arboricity

P. Graham
Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
preprint

Monotone classes of bounded game chromatic number have bounded arboricity

P. Graham
preprint en

Abstract

In the coloring game on a finite graph, Alice and Bob alternately color uncolored vertices with one of $k$ colors so that adjacent vertices get different colors. Alice moves first and wins if every vertex gets colored; Bob wins if some uncolored vertex sees all $k$ colors among its neighbors. The game chromatic number of a graph is the least $k$ for which Alice can force a win. We prove that for every $K$ there is $d$ such that every graph of average degree at least $d$ has a subgraph on which Bob wins the $k$-color game for every $k\le K$. Consequently, if a class of graphs is closed under taking subgraphs and its game chromatic numbers are bounded, then the edges of each of its graphs can be partitioned into a bounded number of forests, that is, the class has bounded arboricity. This answers Zhu's Question 3 (1999) in the affirmative. The proof combines the theorem of Kühn and Osthus that every graph of large enough average degree contains a subgraph of large average degree with no 4-cycle, with a strategy for Bob that adapts the weighting argument behind Beck's criterion for positional games: Bob uses weights to keep some uncolored vertex that can still be blocked from every color. The rest of the proof is checked in Lean, with the theorem of Kühn and Osthus as an explicit hypothesis. This work has not yet been reviewed by experts. The proofs, the Lean formalization and the text were produced by AI models (from OpenAI and Anthropic), working under the author's direction. Written proof, with Lean and computer checks; not yet reviewed by experts. Produced by AI models under the author's direction.

Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon