Matching works

1 work

math.CO — Combinatorics

Monotone classes of bounded game chromatic number have bounded arboricity

Contributed by Peter Graham

In the coloring game on a finite graph, Alice and Bob alternately color uncolored vertices with one of kk 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 kk colors among its neighbors. The game chromatic number of a graph is the least kk for which Alice can force a win. We prove that for every KK there is dd such that every graph of average degree at least dd has a subgraph on which Bob wins the kk-color game for every k≤Kk\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, working under the author's direction.

Author comments: Zenodo archive: https://doi.org/10.5281/zenodo.24376623. The paper text is deposited under CC BY 4.0; the Lean code stays Apache-2.0 in its published repository. Lean 4 development, in its folder lean: https://github.com/6/clank-lab/tree/game-chromatic-arboricity-v1/results/game-chromatic-arboricity

Primarily AI-generated textHuman understanding: some partsarboricitygame chromatic numbergraph coloring gamemonotone graph class
Nov 21, 202610 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations