WorksMathematics
Monotone classes of bounded game chromatic number have bounded arboricity
Abstract
In the coloring game on a finite graph, Alice and Bob alternately color uncolored vertices with one of 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 colors among its neighbors. The game chromatic number of a graph is the least for which Alice can force a win. We prove that for every there is such that every graph of average degree at least has a subgraph on which Bob wins the -color game for every . 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.
Introduction
Main results
Graphs are finite and simple. In the -color game on a graph , Alice and Bob alternately choose an uncolored vertex and give it one of the colors that no neighbor of the vertex has; Alice moves first. The game ends when the player to move has no legal move, and Alice wins if every vertex is then colored; otherwise Bob wins. We use the rules as stated by Zhu [15 pp. 1–2]; the game goes back to Brams, was published by Gardner and was introduced for general graphs by Bodlaender [2 Section 1]. The game chromatic number is the least for which Alice has a winning strategy. A class of graphs is monotone if it is closed under taking subgraphs, that is, any vertex subset with any subset of the edges among it. The arboricity of is the least number of forests into which its edge set can be partitioned. The average degree of a graph with at least one vertex is .
Theorem 1.1. For every integer there is an integer such that every graph with at least one vertex and average degree at least has a subgraph on which Bob has a winning strategy in the -color game for every integer with ; equivalently, .
Whether a win for Alice with colors implies one with colors is Zhu’s Question 1 [15 p. 11], still open [2 Section 8], [7 Question 1.1]; so a win for Bob with colors alone would leave the smaller palettes to check.
Corollary 1.2. For every integer there is an integer with the following property. If a class of graphs is closed under taking subgraphs and each of its members has game chromatic number at most , then each of its members has arboricity at most .
This answers in the affirmative Zhu’s Question 3, whose hereditary classes are those “closed under taking (not necessarily induced) subgraphs” [15 p. 12]:
Question 1.3 (Zhu [15 Question 3]). “Suppose a hereditary class of graphs has bounded game chromatic number. Is it true that the arboricity of this class of graphs is also bounded?”
Both results rest on a theorem of Kühn and Osthus [10 Theorem 1], in the form of Theorem 4.2; given it as a hypothesis, both are proved in Lean (§ 6).
Proof overview
Given a graph of very large average degree, the theorem of Kühn and Osthus gives a subgraph of large average degree with no 4-cycle, and inside it a nonempty vertex set each of whose vertices has many neighbors in (Lemma 3.1). Labeling at random and averaging (Lemma 3.2) gives disjoint sets and a set outside them, more than times as large as , such that every vertex of has a neighbor in every . Keeping one such edge from each to each gives a subgraph in which every has exactly one neighbor in each . Two vertices of share at most one of these neighbors, or there would be a 4-cycle. Fix and play the -color game on with ; call the designated color of . An uncolored whose carry colors can never be colored, since colors are never removed, and Bob wins. Alice protects by making some dead: coloring it with another color, or giving color to a neighbor of it. A move changes the status of at most one vertex of , but may cost every target adjacent to it. While some vertex of is free (uncolored, with no neighbor of its designated color), Bob gives one its designated color; afterwards he plays any legal move. He maximizes a potential, the sum of over the with no dead , where counts the carrying their designated color, placed by either player. As for the Erdős–Selfridge theorem [6 p. 299] and Beck’s criterion [1], Bob’s greedy move gains at least what Alice’s next move can lose, up to an error the overlap bound controls. The potential stays above a reserve proportional to the number of free vertices, so once none is free, some uncolored sees all colors. Finally, if all subgraphs of have average degree below , removing vertices with fewer than remaining neighbors one at a time orders the vertices so that each has fewer than earlier neighbors; giving these edges distinct colors splits the edges into forests.
Prior work and related questions
Zhu’s questions concern hereditary classes because a subgraph can have larger game chromatic number than the graph itself [15 p. 11], as Tuza and Zhu also note in their survey [14 Section 1, p. 306].
Zhu’s Question 2 asks the same with the game coloring number in place of the arboricity. In Bodlaender’s marking game, where Alice and Bob alternately mark vertices, Alice tries to keep small the largest number of previously marked neighbors of any vertex; the least bound she can guarantee is the Go number, and the game coloring number is one more [8 Section 2]. A yes answer to Question 2 would imply one to Question 3 [15 p. 12]. In 2001 Kierstead and Trotter gave “an example which shows that the game chromatic number of a class of graphs may be bounded even when the Go number is not” [8 Section 6], and with a theorem of Dinski and Zhu [3 Theorem 2] their Example 6.1 gives a monotone class with game chromatic number at most 12 and unbounded Go number, a negative answer to Question 2 (Appendix B). Zhu’s Question 4 repeats Conjecture 1 of Dinski and Zhu [3], that every monotone class of bounded game chromatic number has bounded acyclic chromatic number, the fewest colors in a proper coloring with no two-colored cycle. It remains open, and would imply Corollary 1.2, since bounded acyclic chromatic number implies bounded arboricity [15 p. 12]; Appendix B discusses Dvořák’s reduction of it.
The new step is Theorem 2.1, which adapts the weighting argument behind Beck’s criterion for Maker–Breaker games [1], [9 Theorem 4.3]. Unlike Maker, Bob must move legally, and a new estimate bounds the weight Alice’s next move can destroy, since two targets share at most one vertex of .
Bob’s potential strategy
Theorem 2.1. Let and be integers, and let be a graph with a set of vertices and pairwise disjoint sets of vertices, disjoint from . Write and assume:
every neighbor of every vertex of lies in ;
every has exactly one neighbor in , written , for each ;
two distinct vertices of have at most one common neighbor in ;
every vertex of has at most neighbors in , and .
Then Bob has a winning strategy in the -color game on .
The graph may have further vertices, in neither nor , and further edges not meeting .
Proof. A position is a partial proper coloring reached by legal moves. In a position , call a vertex taken if , free if is uncolored and no neighbor of has color , and dead otherwise. Colors never change, so a taken vertex stays taken and a dead vertex stays dead. Call alive if none of is dead, and let be the number of taken vertices among them. Put
and let be the number of free vertices.
(a) An alive vertex is uncolored. If has color , then is not taken (the coloring is proper) and not free (its neighbor has color ), so is dead.
(b) One move changes the status of at most one vertex of . Let a move give the vertex the color . If , then by (1) no vertex of is adjacent to , so only can change status: if it was free, it becomes taken if and dead otherwise, and if it was dead, it stays dead. If , a free vertex stops being free only if and , that is, by (2), only if . If lies in neither nor , then by (1) nothing changes.
(c) The potential. If a move makes a free vertex taken, every alive stays alive with one larger, so grows by . If a move makes a free vertex dead, exactly the alive stop being alive, so falls by . Otherwise is unchanged.
(d) Bob’s strategy. When some vertex is free, Bob takes a free vertex with largest: if he colors it , which is legal because is free. Otherwise he makes any legal move.
(e) The invariants. For a position with Bob to move let say ; for a position with Alice to move let say and for every free . At the start every vertex of is free, every is alive with , , and , so holds by (4). If holds and Alice moves to , then by (b) and (c) either a free became dead, with and , which is the second part of ; or a free became taken, and grew while fell; or nothing changed. So holds.
Now let hold, let some vertex be free, and let Bob take as in (d), reaching . Then and , which gives the first part of . Let be free in ; then , was free in , and . The alive vertices of and are the same, and changed only on those adjacent to . By (3) at most one alive is adjacent to both and ; if there is one, and are two of , both free in , so in and the term of in grew by . Hence and
(f) Bob wins. Let Bob follow (d), and let be the first position of the play with no free vertex; there is one, because the last position has none (a free vertex can be colored). By (e) and induction along the play, or holds at every position up to , according to who moves; the step for Bob is used only at positions with a free vertex. So and some is alive at . As no vertex is free, are all taken, so sees all colors, and by (a) is uncolored. It can never be colored, and Bob wins.
For this adapts the weighting argument behind Beck’s criterion [1], [9, Theorem 4.3]: plays the role of the board and the sets the winning sets of a -uniform family in which two sets share at most one element. New are the legality of Bob’s moves, tracked by the statuses free, taken and dead, and the overlap estimate in (e). The term pays for Alice’s first move.
Corollary 2.2. Let and let consist of pairwise disjoint vertex sets and edges joining each to exactly one vertex of each , with no other edges (further isolated vertices are allowed). If has no -cycle and , where , then .
Proof. Fix and apply Theorem 2.1 with the sets ; the vertices of the other sets lie in neither nor the union of the sets used. Conditions (1) and (2) are immediate, and (3) holds because two vertices of with two common neighbours span a -cycle. For (4), let and pick . Two distinct neighbors of have , since otherwise and would be two common neighbors. So has at most neighbors, and (4) holds with because .
Extraction
Lemma 3.1. A graph with at least one vertex and average degree at least has a nonempty vertex set in which every vertex has at least neighbors in .
Proof. Write for the number of edges inside , and take nonempty of least size with ; the whole vertex set qualifies. If some had fewer than neighbors in , then would be nonempty, since , and , against the choice of .
Lemma 3.2. Let be integers and let be a nonempty set of vertices of a graph such that each vertex in has at least neighbors in . Then there are disjoint sets and a set such that every has a neighbor in each and .
Proof. For take . Let , and , and consider all labelings . For a labeling, let for , let be their union, and let be the set of with that have a neighbor in every . Each lies in for labelings, so
and some labeling has .
The cited theorem
Theorem 4.1 (Kühn and Osthus [10, Theorem 1]). “For every there exists such that every graph of average degree at least contains a subgraph of average degree at least whose girth is at least six.”
We use it in this form, the hypothesis C4FreeSubgraphTheorem of the Lean proof (§ 6).
Theorem 4.2. For every integer there is an integer such that every graph with at least one vertex and average degree at least has a subgraph with at least one vertex, no -cycle and average degree at least .
Derivation from Theorem 4.1. For take : a single vertex is such a subgraph. For take from Theorem 4.1 with . Since , a graph of average degree at least has a subgraph of girth at least six and average degree at least . That subgraph has an edge, hence a vertex, and its girth excludes -cycles.
Appendix C gives an explicit .
Proofs of the main results
Proof of Theorem 1.1. The conclusion for contains the conclusion for every smaller , so we may assume . Let , , , and let be given by Theorem 4.2 for this . Let have at least one vertex and average degree at least . Theorem 4.2 gives a subgraph with no 4-cycle and average degree at least ; Lemma 3.1 gives a set in which every vertex has at least neighbors in ; and Lemma 3.2 gives and with . Choose for each one neighbor for each , and let be the subgraph of on the vertex set of whose edges are the pairs . Then has no 4-cycle, and , also when is empty, since then is not. By Corollary 2.2, .
Proof of Corollary 1.2. Let be as in Theorem 1.1, let be a monotone class whose members have game chromatic number at most , and let . Every subgraph of lies in , so by Theorem 1.1 every subgraph of with at least one vertex has average degree less than . Hence every nonempty vertex set contains a vertex with fewer than neighbors in , since otherwise the subgraph induced by would have average degree at least . Removing such vertices one at a time orders the vertices as so that each has fewer than neighbors among . Color the edges from each to earlier vertices with distinct colors from . In each color class every vertex has at most one edge to an earlier vertex, so the class has no cycle, as the latest vertex of a cycle would have two. So has arboricity at most .
Formal verification
Theorem 1.1 and Corollary 1.2 are proved in Lean 4 [11] with the Mathlib library [12], from definitions of the game given verbatim in Appendix § 7. A position gives each vertex one of the colors, indexed by Fin k, that is , or none, meaning uncolored. A move gives one uncolored vertex a color that none of its neighbors has. The inductive predicate AliceWins G k b c says that Alice can force a win from the position c, with Alice to move when b is true: every vertex is colored; or it is Alice’s turn and some move of hers leads to such a position; or it is Bob’s turn, he has a move, and all his moves lead to such positions. AliceWinsGame G k is this predicate at the empty position with Alice to move. On a finite graph, AliceWinsGame G k says exactly that Bob has a winning strategy in the -color game (Appendix § 7). The cited theorem is the proposition
def C4FreeSubgraphTheorem : Prop :=
∀ t : ℕ, ∃ d : ℕ, ∀ (V : Type) [Finite V] [Nonempty V] (G : SimpleGraph V),
d * Nat.card V ≤ 2 * G.edgeSet.ncard →
∃ H : G.Subgraph, H.verts.Nonempty ∧ C4Free H.coe ∧
t * H.verts.ncard ≤ 2 * H.coe.edgeSet.ncard
where C4Free H says that there are no with , and ; this is Theorem 4.2, with “average degree at least ” written as . The two main results, in Main.lean, are
theorem GCG.exists_subgraph_bob_wins (hC4 : C4FreeSubgraphTheorem) (K : ℕ) :
∃ d : ℕ, ∀ (V : Type) [Finite V] [Nonempty V] (G : SimpleGraph V),
d * Nat.card V ≤ 2 * G.edgeSet.ncard →
∃ H : G.Subgraph, ∀ k ≤ K, ¬ AliceWinsGame H.coe k
theorem GCG.bounded_arboricity (hC4 : C4FreeSubgraphTheorem) (K : N) :
∃ d : N, ∀ C : (V : Type) → SimpleGraph V → Prop,
(∀ V G, C V G → Finite V) →
(∀ V G, C V G → ∀ H : G.Subgraph, C H.verts H.coe) →
(∀ V G, C V G → ∃ k ≤ K, AliceWinsGame G k) →
∀ V G, C V G → ArboricityLE G d
The first is Theorem 1.1, where H.coe is the graph formed by a Mathlib subgraph H. In the second, a class is a predicate C whose three hypotheses say that its members are finite, closed under subgraphs, and of game chromatic number at most ; ArboricityLE G d gives arboricity at most (Appendix § 7). The build fails unless the axioms of the two main theorems and of Theorem 2.1 are exactly Lean’s propext, Classical.choice and Quot.sound. Theorem 2.1 and Lemma 3.2 are formalized as written. Lemma 3.1 is checked for integer , and Corollary 2.2 under the stronger hypothesis ; these are the cases § 5 uses, and Appendix § 7 notes the differences in detail and gives the commands that reproduce the check.
The Lean definitions and correspondence
A position is a function c : V → Option (Fin k): Fin k is the set {0, . . . , k − 1} indexing the colors, and the value none means uncolored. The game is defined in GCG/Game.lean:
def Move (G : SimpleGraph V) {k : N} (c c’ : V → Option (Fin k)) : Prop :=
∃ v i, c v = none ∧ (∀ w, G.Adj v w → c w ≠ some i) ∧ c’ v = some i ∧
∀ u, u ≠ v → c’ u = c u
inductive AliceWins (G : SimpleGraph V) (k : N) :
Bool → (V → Option (Fin k)) → Prop
| full (b : Bool) (c : V → Option (Fin k)) :
(∀ v, c v ≠ none) → AliceWins G k b c
| alice (c c’ : V → Option (Fin k)) :
Move G c c’ → AliceWins G k false c’ → AliceWins G k true c
| bob (c : V → Option (Fin k)) :
(∃ c’, Move G c c’) → (∀ c’, Move G c c’ → AliceWins G k true c’) →
AliceWins G k false c
def AliceWinsGame (G : SimpleGraph V) (k : N) : Prop :=
AliceWins G k true (fun _ => none)
Why ¬ AliceWinsGame G k means that Bob wins. Each move colors a vertex, so on a finite graph every play ends after at most moves. If AliceWins holds at a position, the constructors used in its derivation give Alice a strategy that wins from there: they never let Bob reach a position where it fails, and a play can end only at a full coloring. Suppose it fails at a position. If the player to move has no legal move, play ends there, and since full does not apply, some vertex is uncolored: Bob has won. If it is Alice’s turn, then by alice it fails after each of her moves. If it is Bob’s turn and he has a move, then by bob it fails after some move of his, and he plays that move. Following this, Bob keeps AliceWins false until play ends, so he wins. Zhu [15 pp. 1–2] awards Bob the game as soon as an uncolored vertex has all colors among its neighbors. Such a vertex stays uncolorable, so under the rules of § 1 play ends with it uncolored and Bob wins as well; conversely, a play that ends with an uncolored vertex reached such a vertex. The two conventions give the same winner.
Arboricity. ArboricityLE says that some map from all unordered pairs of vertices to colors makes every color class of edges of a forest. Restricting the map to the edges partitions them into at most forests, so has arboricity at most ; conversely, for a partition into forests extends to such a map. For the predicate fails on every graph with a vertex, which does not affect an existential upper bound.
Correspondence. Both main theorems take the cited theorem as the hypothesis hC4, and their proofs establish its hypotheses (finiteness, a vertex and the density bound) for each graph to which they apply it. C4Free is in GCG/Game.lean and ArboricityLE in GCG/Forest.lean. Theorem 2.1 is GCG.bob_wins_of_structure in GCG/Potential.lean, in which conditions (1)–(4) appear as hypotheses on a set , a family of classes and a map assigning to each and its neighbor . Lemma 3.1 is GCG.exists_minDegree_subset in GCG/Extract.lean, for a positive integer threshold , the case used in § 5; the written proof covers real . Lemma 3.2 is GCG.extract in the same file. GCG.bob_wins_pickGraph in Main.lean is Corollary 2.2 with the hypothesis replaced by the stronger , which is what Lemma 3.2 provides in § 5; the graph whose edges are the pairs is GCG.pickGraph. The printed Corollary 2.2 follows from the checked Theorem 2.1 by the written proof. The degeneracy step in the proof of Corollary 1.2 is GCG.arboricityLE_of_degenerate in GCG/Forest.lean. The axiom checks are in Axioms.lean.
The formal proof of Theorem 1.1 applies the cited theorem with , which is the value of in § 5 for in place of ; this covers without a separate case. Its subgraph keeps all the vertices of , as in the written proof.
To reproduce the check, run lake exe cache get and lake build in the lean folder of the published development (linked below the title), which pins Lean v4.34.0 and a Mathlib commit; with the Mathlib cache the build takes about a minute.
Zhu's Questions 2 and 4
Kierstead and Trotter [8 Example 6.1] subdivide every edge of once; their proof shows that these graphs have acyclic chromatic number at most 3 and game chromatic number at most 4, and that their Go number tends to infinity. By a theorem of Dinski and Zhu [3 Theorem 2], every subgraph of a graph with acyclic chromatic number at most has game chromatic number at most . So the subgraphs of the graphs form a monotone class with game chromatic number at most 12 and unbounded game coloring number, which answers Question 2 in the negative.
Dvořák [4 Section 3.1.5] showed that the conjecture of Dinski and Zhu follows from Conjecture 3.1 of [4] (Conjecture 1 of [5], derived there from its Corollary 4): “There exists a function such that for each graph , if then the game chromatic number of is at least ”, where is the chromatic number, ranges over the positive integers and is obtained by subdividing every edge of once. Dvořák calls it “wide open”. The present argument does not reach these graphs. In a subgraph of , every edge meets a subdivision vertex and these have degree at most 2, so there are at most twice as many edges as subdivision vertices; a subgraph with an edge also has a vertex of , so its average degree is less than 4, and Theorem 1.1 says nothing about it.
An explicit bound
Montgomery, Pokrovskiy and Sudakov [13 Theorem 1.1] showed that there is such that for every integer , every graph of average degree at least has a subgraph of average degree at least and girth at least 6; so serves in Theorem 4.2 for . § 5 applies it with of order , so is at most doubly exponential in ; we made no attempt to optimize it.
References
References
- [1]J. Beck, Van der Waerden and Ramsey type games, Combinatorica 1 (1981), 103–116, https://doi.org/10.1007/BF02579267.
- [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.
- [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.
- [4]Z. Dvořák, Asymptotical Structure of Combinatorial Objects, doctoral thesis, Charles University, Prague, 2007, https://iuuk.mff.cuni.cz/~rakdver/disert.pdf.
- [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.
- [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.
- [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.
- [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.
- [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.arxiv.org/abs/1404.2731
- [10]D. Kühn and D. Osthus, Every graph of sufficiently large average degree contains a C₄-free subgraph of large average degree, Combinatorica 24 (2004), 155–162; authors’ final version.
- [11]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.
- [12]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.
- [13]R. Montgomery, A. Pokrovskiy and B. Sudakov, C₄-free subgraphs with large average degree, Israel J. Math. 246 (2021), 55–71; arXiv:2004.03564v1.arxiv.org/abs/2004.03564
- [14]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.
- [15]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.