betaFeedback

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 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.

Introduction

Main results

Graphs are finite and simple. In the kk-color game on a graph GG, Alice and Bob alternately choose an uncolored vertex and give it one of the colors 1,…,k1, \ldots, k 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 χg(G)\chi_g(G) is the least kk 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 GG 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 2∣E(G)∣/∣V(G)∣2|E(G)|/|V(G)|.

Theorem 1.1. For every integer K≥0K \ge0 there is an integer d=d(K)d=d(K) such that every graph with at least one vertex and average degree at least dd has a subgraph HH on which Bob has a winning strategy in the kk-color game for every integer kk with 0≤k≤K0 \le k \le K; equivalently, χg(H)>K\chi_g(H)>K.

Whether a win for Alice with kk colors implies one with k+1k+1 colors is Zhu’s Question 1 [15 p. 11], still open [2 Section 8], [7 Question 1.1]; so a win for Bob with KK colors alone would leave the smaller palettes to check.

Corollary 1.2. For every integer K≥0K \ge0 there is an integer d(K)d(K) 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 KK, then each of its members has arboricity at most d(K)d(K).

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 G0G_0 of large average degree with no 4-cycle, and inside it a nonempty vertex set SS each of whose vertices has many neighbors in SS (Lemma 3.1). Labeling SS at random and averaging (Lemma 3.2) gives disjoint sets U1,…,UK⊆SU_1,\ldots,U_K \subseteq S and a set A⊆SA \subseteq S outside them, more than 2K+12^K+1 times as large as U=U1∪⋯∪UKU=U_1\cup\cdots\cup U_K, such that every vertex of AA has a neighbor in every UiU_i. Keeping one such edge from each a∈Aa\in A to each UiU_i gives a subgraph HH in which every a∈Aa\in A has exactly one neighbor aia_i in each UiU_i. Two vertices of AA share at most one of these neighbors, or there would be a 4-cycle. Fix k≤Kk\le K and play the kk-color game on HH with U1,…,UkU_1,\ldots,U_k; call ii the designated color of UiU_i. An uncolored a∈Aa\in A whose a1,…,aka_1,\ldots,a_k carry colors 1,…,k1,\ldots,k can never be colored, since colors are never removed, and Bob wins. Alice protects aa by making some aia_i dead: coloring it with another color, or giving color ii to a neighbor of it. A move changes the status of at most one vertex of UU, but may cost every target adjacent to it. While some vertex of UU 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 2t(a)2^{t(a)} over the aa with no dead aia_i, where t(a)t(a) counts the aia_i 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 aa sees all kk colors. Finally, if all subgraphs of GG have average degree below dd, removing vertices with fewer than dd remaining neighbors one at a time orders the vertices so that each has fewer than dd earlier neighbors; giving these edges distinct colors splits the edges into dd 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 UU.

Bob’s potential strategy

Theorem 2.1. Let k≥0k \ge0 and D≥0D \ge0 be integers, and let GG be a graph with a set AA of vertices and pairwise disjoint sets U1,…,UkU_1, \ldots, U_k of vertices, disjoint from AA. Write U=U1∪⋯∪UkU = U_1 \cup\cdots\cup U_k and assume:

  1. every neighbor of every vertex of UU lies in AA;

  1. every a∈Aa \in A has exactly one neighbor in UiU_i, written aia_i, for each ii;

  1. two distinct vertices of AA have at most one common neighbor in UU;

  1. every vertex of UU has at most DD neighbors in AA, and 2k∣U∣+8D<8∣A∣2^k|U| + 8D < 8|A|.

Then Bob has a winning strategy in the kk-color game on GG.

The graph GG may have further vertices, in neither AA nor UU, and further edges not meeting UU.

Proof. A position is a partial proper coloring reached by legal moves. In a position cc, call a vertex w∈Uiw \in U_i taken if c(w)=ic(w)=i, free if ww is uncolored and no neighbor of ww has color ii, and dead otherwise. Colors never change, so a taken vertex stays taken and a dead vertex stays dead. Call a∈Aa \in A alive if none of a1,…,aka_1, \ldots, a_k is dead, and let t(a)t(a) be the number of taken vertices among them. Put

Φ(c)=∑a alive2t(a),Φy(c)=∑a alive, a∼y2t(a)(y∈U).\Phi(c)=\sum_{a\ \mathrm{alive}}2^{t(a)},\qquad\Phi_y(c)=\sum_{a\ \mathrm{alive},\ a\sim y}2^{t(a)}\quad(y\in U).

and let F(c)F(c) be the number of free vertices.

(a) An alive vertex is uncolored. If a∈Aa \in A has color jj, then aja_j is not taken (the coloring is proper) and not free (its neighbor aa has color jj), so aja_j is dead.

(b) One move changes the status of at most one vertex of UU. Let a move give the vertex vv the color jj. If v∈Uiv \in U_i, then by (1) no vertex of UU is adjacent to vv, so only vv can change status: if it was free, it becomes taken if j=ij=i and dead otherwise, and if it was dead, it stays dead. If v∈Av \in A, a free vertex w∈Uiw \in U_i stops being free only if i=ji=j and w∼vw \sim v, that is, by (2), only if w=vjw=v_j. If vv lies in neither AA nor UU, then by (1) nothing changes.

(c) The potential. If a move makes a free vertex yy taken, every alive a∼ya \sim y stays alive with t(a)t(a) one larger, so Φ\Phi grows by Φy(c)\Phi_y(c). If a move makes a free vertex yy dead, exactly the alive a∼ya \sim y stop being alive, so Φ\Phi falls by Φy(c)\Phi_y(c). Otherwise Φ\Phi is unchanged.

(d) Bob’s strategy. When some vertex is free, Bob takes a free vertex xx with Φx(c)\Phi_x(c) largest: if x∈Uix \in U_i he colors it ii, which is legal because xx is free. Otherwise he makes any legal move.

(e) The invariants. For a position cc with Bob to move let IB(c)I_B(c) say 8Φ(c)>2kF(c)8\Phi(c) > 2^kF(c); for a position with Alice to move let IA(c)I_A(c) say 8Φ(c)>2kF(c)8\Phi(c) > 2^kF(c) and 8(Φ(c)−Φy(c))>2k(F(c)−1)8(\Phi(c) - \Phi_y(c)) > 2^k(F(c) - 1) for every free yy. At the start every vertex of UU is free, every a∈Aa \in A is alive with t(a)=0t(a)=0, Φ=∣A∣\Phi=|A|, F=∣U∣F=|U| and Φy≤D\Phi_y \le D, so IAI_A holds by (4). If IA(c)I_A(c) holds and Alice moves to c′c', then by (b) and (c) either a free yy became dead, with Φ(c′)=Φ(c)−Φy(c)\Phi(c') = \Phi(c) - \Phi_y(c) and F(c′)=F(c)−1F(c') = F(c) - 1, which is the second part of IA(c)I_A(c); or a free yy became taken, and Φ\Phi grew while FF fell; or nothing changed. So IB(c′)I_B(c') holds.

Now let IB(c)I_B(c) hold, let some vertex be free, and let Bob take xx as in (d), reaching c′c'. Then Φ(c′)=Φ(c)+Φx(c)\Phi(c') = \Phi(c) + \Phi_x(c) and F(c′)=F(c)−1F(c') = F(c) - 1, which gives the first part of IA(c′)I_A(c'). Let yy be free in c′c'; then y≠xy \ne x, yy was free in cc, and Φy(c)≤Φx(c)\Phi_y(c) \le\Phi_x(c). The alive vertices of cc and c′c' are the same, and tt changed only on those adjacent to xx. By (3) at most one alive aa is adjacent to both xx and yy; if there is one, xx and yy are two of a1,…,aka_1,\ldots,a_k, both free in cc, so t(a)≤k−2t(a) \le k - 2 in cc and the term of aa in Φy\Phi_y grew by 2t(a)≤2k/42^{t(a)} \le2^k/4. Hence 8(Φy(c′)−Φy(c))≤2⋅2k8(\Phi_y(c') - \Phi_y(c)) \le2 \cdot2^k and

8(Φ(c′)−Φy(c′))≥8Φ(c)−2⋅2k>2kF(c)−2⋅2k=2k(F(c′)−1).8(\Phi(c') - \Phi_y(c')) \ge8\Phi(c) - 2 \cdot2^k > 2^kF(c) - 2 \cdot2^k = 2^k(F(c') - 1).

(f) Bob wins. Let Bob follow (d), and let pp 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, IAI_A or IBI_B holds at every position up to pp, according to who moves; the step for Bob is used only at positions with a free vertex. So Φ(p)>0\Phi(p) > 0 and some aa is alive at pp. As no vertex is free, a1,…,aka_1,\ldots,a_k are all taken, so aa sees all kk colors, and by (a) aa is uncolored. It can never be colored, and Bob wins.

For k≥2k \ge2 this adapts the weighting argument behind Beck’s criterion [1], [9, Theorem 4.3]: UU plays the role of the board and the sets {a1,…,ak}\{a_1,\ldots,a_k\} the winning sets of a kk-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 8D8D pays for Alice’s first move.

Corollary 2.2. Let K≥2K \ge2 and let GG consist of pairwise disjoint vertex sets A,U1,…,UKA,U_1,\ldots,U_K and edges joining each a∈Aa \in A to exactly one vertex aia_i of each UiU_i, with no other edges (further isolated vertices are allowed). If GG has no 44-cycle and (2K+8)∣U∣<8∣A∣(2^K+8)|U| < 8|A|, where U=U1∪⋯∪UKU=U_1\cup\cdots\cup U_K, then χg(G)≥K\chi_g(G) \ge K.

Proof. Fix k≤Kk \le K and apply Theorem 2.1 with the sets U1,…,UkU_1,\ldots,U_k; the vertices of the other sets lie in neither AA nor the union of the sets used. Conditions (1) and (2) are immediate, and (3) holds because two vertices of AA with two common neighbours span a 44-cycle. For (4), let w∈Uiw \in U_i and pick j≠ij \ne i. Two distinct neighbors a,a′a,a' of ww have aj≠aj′a_j \ne a'_j, since otherwise ww and aja_j would be two common neighbors. So ww has at most ∣Uj∣≤∣U∣|U_j| \le|U| neighbors, and (4) holds with D=∣U∣D=|U| because 2k∣U1∪⋯∪Uk∣+8∣U∣≤(2K+8)∣U∣2^k|U_1\cup\cdots\cup U_k|+8|U| \le(2^K+8)|U|.

Extraction

Lemma 3.1. A graph with at least one vertex and average degree at least t>0t > 0 has a nonempty vertex set SS in which every vertex has at least t/2t/2 neighbors in SS.

Proof. Write e(S)e(S) for the number of edges inside SS, and take SS nonempty of least size with 2e(S)≥t∣S∣2e(S) \ge t|S|; the whole vertex set qualifies. If some v∈Sv \in S had fewer than t/2t/2 neighbors in SS, then S∖{v}S \setminus\{v\} would be nonempty, since e(S)>0e(S) > 0, and 2e(S∖{v})>2e(S)−t≥t∣S∖{v}∣2e(S \setminus\{v\}) > 2e(S) - t \ge t|S \setminus\{v\}|, against the choice of SS.

Lemma 3.2. Let K,M≥0K, M \ge0 be integers and let SS be a nonempty set of vertices of a graph such that each vertex in SS has at least δ=2(M+1)K(K+1)\delta= 2(M + 1)K(K + 1) neighbors in SS. Then there are disjoint sets U1,…,UK⊆SU_1, \ldots, U_K \subseteq S and a set A⊆S∖(U1∪⋯∪UK)A \subseteq S \setminus(U_1 \cup\cdots\cup U_K) such that every a∈Aa \in A has a neighbor in each UiU_i and M∣U1∪⋯∪UK∣<∣A∣M|U_1 \cup\cdots\cup U_K| < |A|.

Proof. For K=0K = 0 take A=SA = S. Let K≥1K \ge1, N=2(M+1)KN = 2(M + 1)K and n=∣S∣n = |S|, and consider all NnN^n labelings ℓ:S→{0,…,N−1}\ell: S \to\{0, \ldots, N - 1\}. For a labeling, let Ui(ℓ)=ℓ−1(i−1)U_i(\ell) = \ell^{-1}(i - 1) for i≤Ki \le K, let U(ℓ)U(\ell) be their union, and let A(ℓ)A(\ell) be the set of x∈Sx \in S with ℓ(x)≥K\ell(x) \ge K that have a neighbor in every Ui(ℓ)U_i(\ell). Each xx lies in U(ℓ)U(\ell) for KNn−1KN^{n-1} labelings, so

∑ℓ(∣A(ℓ)∣−M∣U(ℓ)∣)≥n(Nn−(M+1)KNn−1−K(N−1)δNn−δ)>0,\sum_{\ell} \left(|A(\ell)| - M|U(\ell)|\right) \ge n\left(N^n - (M + 1)KN^{n-1} - K(N - 1)^\delta N^{n-\delta}\right) > 0,

and some labeling has ∣A(ℓ)∣>M∣U(ℓ)∣|A(\ell)| > M|U(\ell)|.

The cited theorem

Theorem 4.1 (Kühn and Osthus [10, Theorem 1]). “For every kk there exists d=d(k)d = d(k) such that every graph of average degree at least dd contains a subgraph of average degree at least kk 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 t≥0t \ge0 there is an integer dd such that every graph with at least one vertex and average degree at least dd has a subgraph with at least one vertex, no 44-cycle and average degree at least tt.

Derivation from Theorem 4.1. For t=0t = 0 take d=0d = 0: a single vertex is such a subgraph. For t≥1t \ge1 take d=⌈d(t)⌉d = \lceil d(t) \rceil from Theorem 4.1 with k=tk = t. Since d≥d(t)d \ge d(t), a graph of average degree at least dd has a subgraph of girth at least six and average degree at least t≥1t \ge1. That subgraph has an edge, hence a vertex, and its girth excludes 44-cycles.

Appendix C gives an explicit dd.

Proofs of the main results

Proof of Theorem 1.1. The conclusion for KK contains the conclusion for every smaller KK, so we may assume K≥2K \ge2. Let M=2K+1M = 2^K + 1, δ=2(M+1)K(K+1)\delta= 2(M + 1)K(K + 1), t=2δt = 2\delta, and let dd be given by Theorem 4.2 for this tt. Let GG have at least one vertex and average degree at least dd. Theorem 4.2 gives a subgraph G0G_0 with no 4-cycle and average degree at least tt; Lemma 3.1 gives a set SS in which every vertex has at least δ\delta neighbors in SS; and Lemma 3.2 gives AA and U1,…,UKU_1,\ldots,U_K with M∣U∣<∣A∣M|U| < |A|. Choose for each a∈Aa \in A one neighbor ai∈Uia_i \in U_i for each ii, and let HH be the subgraph of G0G_0 on the vertex set of G0G_0 whose edges are the pairs aaiaa_i. Then HH has no 4-cycle, and (2K+8)∣U∣≤8M∣U∣<8∣A∣(2^K + 8)|U| \le8M|U| < 8|A|, also when UU is empty, since then AA is not. By Corollary 2.2, χg(H)>K\chi_g(H) > K.

Proof of Corollary 1.2. Let d=d(K)d = d(K) be as in Theorem 1.1, let C\mathcal{C} be a monotone class whose members have game chromatic number at most KK, and let G∈CG \in\mathcal{C}. Every subgraph of GG lies in C\mathcal{C}, so by Theorem 1.1 every subgraph of GG with at least one vertex has average degree less than dd. Hence every nonempty vertex set SS contains a vertex with fewer than dd neighbors in SS, since otherwise the subgraph induced by SS would have average degree at least dd. Removing such vertices one at a time orders the vertices as v1,…,vnv_1,\ldots,v_n so that each vmv_m has fewer than dd neighbors among v1,…,vm−1v_1,\ldots,v_{m-1}. Color the edges from each vmv_m to earlier vertices with distinct colors from 1,…,d1,\ldots,d. 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 GG has arboricity at most dd.

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 kk colors, indexed by Fin k, that is {0,…,k−1}\{0,\ldots,k - 1\}, 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, ¬\neg AliceWinsGame G k says exactly that Bob has a winning strategy in the kk-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 a,b,c,da,b,c,d with a≠ca \ne c, b≠db \ne d and a∼b∼c∼d∼aa \sim b \sim c \sim d \sim a; this is Theorem 4.2, with “average degree at least dd” written as d∣V∣≤2∣E∣d|V| \le2|E|. 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 KK; ArboricityLE G d gives arboricity at most dd (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 tt, and Corollary 2.2 under the stronger hypothesis (2K+1)∣U∣<∣A∣(2^{K} + 1)|U| < |A|; 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 kk 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 ∣V∣|V| 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 kk 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 GG dd says that some map from all unordered pairs of vertices to dd colors makes every color class of edges of GG a forest. Restricting the map to the edges partitions them into at most dd forests, so GG has arboricity at most dd; conversely, for d>0d > 0 a partition into dd forests extends to such a map. For d=0d = 0 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 AA, a family of classes and a map assigning to each a∈Aa \in A and ii its neighbor aia_i. Lemma 3.1 is GCG.exists_minDegree_subset in GCG/Extract.lean, for a positive integer threshold tt, the case used in § 5; the written proof covers real t>0t > 0. Lemma 3.2 is GCG.extract in the same file. GCG.bob_wins_pickGraph in Main.lean is Corollary 2.2 with the hypothesis (2K+8)∣U∣<8∣A∣(2K + 8)|U| < 8|A| replaced by the stronger (2K+1)∣U∣<∣A∣(2K + 1)|U| < |A|, which is what Lemma 3.2 provides in § 5; the graph whose edges are the pairs aaiaa_i 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 t=4(2K+2+2)(K+2)(K+3)t = 4(2^{K+2} + 2)(K + 2)(K + 3), which is the value of tt in § 5 for K+2K + 2 in place of KK; this covers K<2K < 2 without a separate case. Its subgraph HH keeps all the vertices of G0G_0, 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 Kn,nK_{n,n} once; their proof shows that these graphs GnG_n 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 kk has game chromatic number at most k(k+1)k(k + 1). So the subgraphs of the graphs GnG_n 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 ff such that for each graph GG, if χ(G)≥f(c)\chi(G) \ge f(c) then the game chromatic number of sd⁡1(G)\operatorname{sd}_1(G) is at least cc”, where χ(G)\chi(G) is the chromatic number, cc ranges over the positive integers and sd⁡1(G)\operatorname{sd}_1(G) is obtained by subdividing every edge of GG once. Dvořák calls it “wide open”. The present argument does not reach these graphs. In a subgraph of sd⁡1(G)\operatorname{sd}_1(G), 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 GG, 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 c>0c > 0 such that for every integer t≥1t \ge1, every graph of average degree at least 2ct2log⁡t2^{ct^2 \log t} has a subgraph of average degree at least tt and girth at least 6; so d=⌈2ct2log⁡t⌉d = \lceil2^{ct^2 \log t} \rceil serves in Theorem 4.2 for t≥1t \ge1. § 5 applies it with tt of order K2KK^{2^K}, so d(K)d(K) is at most doubly exponential in KK; we made no attempt to optimize it.

References

References

  1. [1]J. Beck, Van der Waerden and Ramsey type games, Combinatorica 1 (1981), 103–116, https://doi.org/10.1007/BF02579267.
  2. [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. [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. [4]Z. Dvořák, Asymptotical Structure of Combinatorial Objects, doctoral thesis, Charles University, Prague, 2007, https://iuuk.mff.cuni.cz/~rakdver/disert.pdf.
  5. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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.

Paper details

vlnc:W_vxyxc7ea
Version
v1 · latest
Published
Fresh — published within the last 30 days
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI models (from OpenAI and Anthropic)

View statement
Looking for related papers…
Contents