Monotone classes of bounded game chromatic number have bounded arboricity

Primarily AI-generated textHuman understanding: some partsmath.CO — Combinatorics

Contributed by Peter Graham ↗

Version 1 / Nov 21, 2026 / CC BY 4.0

Abstract

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

Provenance statement

The proofs, the Lean formalization and the text were produced by AI models, working under the author's direction. Human understanding (author): I follow the statements, not every proof step.

References

  1. J. Beck, Van der Waerden and Ramsey type games, Combinatorica 1 (1981), 103--116, https://doi.org/10.1007/BF02579267.DOI
  2. T. Bartnicki, J. Grytczuk, H. A. Kierstead and X. Zhu, The map-coloring game, Amer. Math. Monthly 114 (2007), 793--803; https://doi.org/10.1080/00029890.2007.11920471; archived author copy (https://web.archive.org/web/20191124231544id_/http://www.math.nsysu.edu.tw/~zhu/papers/game/monthly793-803-grytczuk.pdf).DOI
  3. T. Dinski and X. Zhu, A bound for the game chromatic number of graphs, Discrete Math. 196 (1999), 109--115, https://doi.org/10.1016/S0012-365X(98)00197-6. Theorem and conjecture numbers as in the authors' preprint of October 1997 (https://web.archive.org/web/20191124231514id_/http://www.math.nsysu.edu.tw/~zhu/papers/game/bound.pdf).DOI
  4. Z. Dvořák, Asymptotical Structure of Combinatorial Objects , doctoral thesis, Charles University, Prague, 2007, https://iuuk.mff.cuni.cz/~rakdver/disert.pdf.link
  5. Z. Dvořák, On forbidden subdivision characterizations of graph classes, European J. Combin. 29 (2008), 1321--1332, https://doi.org/10.1016/j.ejc.2007.05.008. Numbering as in the author's preprint, ITI Series 2006-324.DOI
  6. P. Erdős and J. L. Selfridge, On a combinatorial game, J. Combin. Theory Ser. A 14 (1973), 298--301, https://doi.org/10.1016/0097-3165(73)90005-8.DOI
  7. L. Hollom, On monotonicity in Maker--Breaker graph colouring games , Discrete Appl. Math. 347 (2024), 131--138, https://doi.org/10.1016/j.dam.2024.01.007.DOI
  8. H. A. Kierstead and W. T. Trotter, Competitive colorings of oriented graphs, Electron. J. Combin. 8(2) (2001), #R12, https://doi.org/10.37236/1611.DOI
  9. M. Krivelevich, Positional games, in Proceedings of the International Congress of Mathematicians, Seoul 2014 , vol. 4, Kyung Moon Sa, 2014, 355--379. Theorem numbering as in arXiv:1404.2731v1 (https://arxiv.org/abs/1404.2731v1).arXiv
  10. D. Kühn and D. Osthus, Every graph of sufficiently large average degree contains a C4C_4-free subgraph of large average degree, Combinatorica 24 (2004), 155--162; authors' final version (https://web.mat.bham.ac.uk/D.Osthus/c4final.pdf).link
Show all 15 referencesShow fewer references
  1. L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language, in Automated Deduction -- CADE 28 , Lecture Notes in Comput. Sci. 12699, Springer, 2021, 625--635, https://doi.org/10.1007/978-3-030-79876-5_37.DOI
  2. The mathlib Community, The Lean mathematical library, in Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs , 2020, 367--381; authors' copy (https://leanprover-community.github.io/papers/mathlib-paper.pdf).link
  3. R. Montgomery, A. Pokrovskiy and B. Sudakov, C4C_4-free subgraphs with large average degree, Israel J. Math. 246 (2021), 55--71; arXiv:2004.03564v1 (https://arxiv.org/abs/2004.03564v1).arXiv
  4. Zs. Tuza and X. Zhu, Colouring games , in Topics in Chromatic Graph Theory (L. W. Beineke and R. J. Wilson, eds.), Encyclopedia Math. Appl. 156, Cambridge University Press, 2015, 304--326, https://doi.org/10.1017/CBO9781139519793.017.DOI
  5. X. Zhu, The game coloring number of planar graphs, J. Combin. Theory Ser. B 75 (1999), 245--258, https://doi.org/10.1006/jctb.1998.1878. Page and question numbers as in the author's preprint (https://web.archive.org/web/20191124231557id_/http://www.math.nsysu.edu.tw/~zhu/papers/game/planar.pdf).DOI

Version history

  1. v1 · 10 pagesSubmitted by P. GrahamZenodo 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-arboricityCurrentNov 21, 2026