betaFeedback

WorksMathematics

List packing for graphs with small arboricity

Abstract

We prove that every graph GG whose edge set is the union of rr forests has list packing number at most 2r2^r. This means that for all k≥2rk\ge 2^r and every list-assignment LL with lists of size kk, the graph GG admits kk disjoint proper LL-colourings. While for large rr this bound is far from optimal, for r∈{1,2}r\in\{1,2\} it is sharp. As a direct corollary of the case r=2r=2, we obtain that every triangle-free planar graph has list packing number at most 44, thus improving upon a result of Dvořák, Masařík, Musílek and Pangrác and providing the optimal answer to a question of Dvořák, Postle and Norin on (weighted) εε-flexibility of such graphs. As a corollary of the case r=3r=3, we obtain a short alternative proof that every K5K_5-minor-free (and hence every planar) graph has list-packing number at most 88, matching the state of the art. All results above also hold for the stronger notion of correspondence packing.

Introduction

We present a follow-up of an earlier paper [10] by the same authors on disjoint list colourings in planar graphs. All graphs in this manuscript are simple and finite. A kk-list-assignment LL assigns to every vertex vv a private set L(v)L(v) of kk allowed colours, and an LL-colouring is a proper vertex-colouring c:V(G)→⋃vL(v)c: V(G) \to\bigcup_{v} L(v) such that c(v)∈L(v)c(v) \in L(v) for every vertex vv. The smallest kk such that every kk-list-assignment of GG admits an LL-colouring is the list chromatic number χℓ(G)\chi_\ell(G). A particularly useful application of this widely studied parameter has been the short inductive proof [25] that planar graphs have list chromatic number (and hence chromatic number) at most 5. Likewise, this note will find its applications in planar graphs.

In the study of graph colourings, more often than not, one is already satisfied if one colouring with the desired properties is proved to exist. We are instead interested in finding multiple colourings that are moreover pairwise disjoint. In this vein, list packings were introduced in [7], as an interpolation between list colourings, independent transversals and strong colourings. More precisely, an LL-packing of GG is a collection of kk pairwise disjoint LL-colourings c1,c2,…,ckc_1,c_2,\ldots,c_k, meaning that ci(v)≠cj(v)c_i(v) \ne c_j(v) for every distinct i,j∈[k]i,j \in[k] and v∈V(G)v \in V(G). As a consequence, these kk colourings partition every list L(v)L(v). The list packing number χℓ∗(G)\chi_\ell^*(G) of GG is the smallest integer kk such that every kk-list-assignment LL of GG admits an LL-packing. The most basic but still completely open problem in this area is whether χℓ∗(G)≤C⋅χℓ(G)\chi_\ell^*(G) \le C \cdot\chi_\ell(G) for some absolute constant C>0C > 0.

Beyond the notion of list colourings, we will work in the more general correspondence setting of Dvořák and Postle [18]. A correspondence-cover of GG is a pair H=(L,H)\mathcal{H}=(L,H), where HH is a graph, the sets {L(v):v∈V(G)}\{L(v) : v \in V(G)\} partition V(H)V(H), every H[L(v)]H[L(v)] is a clique, and, for each edge uv∈E(G)uv \in E(G), the edges of HH between L(u)L(u) and L(v)L(v) form a matching MuvM_{uv}. If uv∉E(G)uv \notin E(G), then there is no edge between L(u)L(u) and L(v)L(v). The cover is kk-fold if ∣L(v)∣=k|L(v)| = k for every vv. An HH-colouring is an independent transversal of HH, meaning an independent set of HH that intersects every list L(v)L(v). A HH-packing is a collection of kk pairwise disjoint independent transversals. Thus, an HH-packing partitions V(H)V(H) into kk independent transversals. The correspondence packing number χc⋆(G)\chi_c^\star(G) is the least integer kk such that every kk-fold correspondence-cover of GG has a packing. Every list-assignment has an associated correspondence-cover, so χℓ(G)≤χℓ⋆(G)≤χc⋆(G)\chi_\ell(G) \le\chi_\ell^\star(G) \le\chi_c^\star(G) for every graph GG.

Since their introduction, the packing numbers have been studied in terms of various graph invariants, including maximum degree, degeneracy, fractional chromatic number, treewidth and pathwidth. For more background and related papers we refer to [7, 6, 5, 10, 9, 22, 21, 20, 12, 13]. Here we study yet another parameter, which turns out to be particularly useful for applications to planar graphs: the arboricity arb⁡(G)\operatorname{arb}(G) of a graph GG is the least number of forests whose edge sets partition E(G)E(G). Our main result gives a direct connection between this classical density parameter and correspondence packing.

Theorem 1.1. Every graph GG satisfies

χc⋆(G)≤2arb⁡(G).\chi_c^\star(G) \le2^{\operatorname{arb}(G)}.

As we will see later, Theorem 1.1 is sharp for arb⁡(G)∈{1,2}\operatorname{arb}(G) \in\{1,2\}. For arb⁡(G)=3\operatorname{arb}(G) = 3, the optimal bound could be 6, 7, or 8. For arb⁡(G)≥4\operatorname{arb}(G) \ge4, a simple degeneracy argument already supplies something better. Indeed, the degeneracy of GG is at most 2arb⁡(G)−12\operatorname{arb}(G)-1 and as proved in [7], twice degeneracy is a sharp upper bound on χc⋆(G)\chi_c^\star(G). Despite the bound of Theorem 1.1 being very bad for large arboricity, we have kept the statement in this general form because it reflects the proof method, which could be interpreted as a careful product colouring over the forests. Moreover, this form might inspire the use of other decomposition theorems beyond forests. For the nontrivial applications of Theorem 1.1, we are primarily interested in graphs with arboricity 2 or 3.

Recall that the maximum average degree mad⁡(G)=max⁡∅≠J⊆G2∣E(J)∣∣V(J)∣\operatorname{mad}(G) = \max_{\varnothing\ne J \subseteq G} \frac{2|E(J)|}{|V(J)|} is defined as the average degree maximized over all subgraphs of GG. The Nash–Williams arboricity theorem [24] relates arboricity with maximum average degree, turning Theorem 1.1 into a density bound

Corollary 1.2.

χc⋆(G)≤{8if mad⁡(G)<5+37,4if mad⁡(G)<3+35,2if mad⁡(G)<2.\chi_c^\star(G) \le \begin{cases} 8 & \text{if } \operatorname{mad}(G) < 5 + \frac{3}{7},\\ 4 & \text{if } \operatorname{mad}(G) < 3 + \frac{3}{5},\\ 2 & \text{if } \operatorname{mad}(G) < 2. \end{cases}

The bound 8 was already known under the weaker condition mad⁡(G)<6\operatorname{mad}(G) < 6, but with a long proof that required a computer-assisted preprocessing step to count certain tuples of small permutations [10]. Our condition mad⁡(G)<3+35\operatorname{mad}(G) < 3 + \frac{3}{5} is sharp due to the complete graph on 5 vertices with one edge removed, and improves the previous best-known [10, 12] condition mad⁡(G)<10/3\operatorname{mad}(G) < 10/3. The result under condition mad⁡(G)<2\operatorname{mad}(G) < 2 is trivial, but it allows us to emphasize a curious gap [11]: there exists no graph GG with χc⋆(G)=3\chi_c^\star(G) = 3. For completeness, we also mention the result from [10, 12] that χc⋆(G)≤5\chi_c^\star(G) \le5 whenever mad⁡(G)<4\operatorname{mad}(G) < 4, which is sharp because χc⋆(K5)=6\chi_c^\star(K_5) = 6. Our second corollary recovers results from [10] for graphs that exclude a small clique minor.

Corollary 1.3.

χc∗(G)≤{8if G is K5-minor-free,4if G is K4-minor-free,2if G is K3-minor-free.\chi^*_{\mathrm c}(G) \le \begin{cases} 8 & \text{if } G \text{ is } K_5\text{-minor-free},\\ 4 & \text{if } G \text{ is } K_4\text{-minor-free},\\ 2 & \text{if } G \text{ is } K_3\text{-minor-free}. \end{cases}

The bounds for K4K_4-minor-free and K3K_3-minor-free graphs are optimal. Recent work [9] shows that there exist K5K_5-minor-free graphs with correspondence packing number 66, and every 66-fold correspondence-cover of every K5K_5-minor-free graph GG admits three pairwise disjoint colourings, but χc∗(G)≤6\chi^*_{\mathrm c}(G) \le6 remains conjectural. Our third corollary is perhaps the most appealing.

Corollary 1.4.

χc∗(G)≤{8if G is planar,4if G is triangle-free planar,2if G is a forest.\chi^*_{\mathrm c}(G) \le \begin{cases} 8 & \text{if } G \text{ is planar},\\ 4 & \text{if } G \text{ is triangle-free planar},\\ 2 & \text{if } G \text{ is a forest}. \end{cases}

For triangle-free planar graphs, Corollary 1.4 improves the previous upper bound [10, 12] from 55 to 44. This was open even for bipartite planar graphs and it is sharp in a strong sense. For instance, every cycle has correspondence packing number 44, and due to a construction in [10], there exist planar graphs of arbitrarily large girth with list packing number 44. The result for general planar graphs recovers the known bound 88 for planar graphs [10, 12], but via a shorter proof that avoids extensive case analysis of matchings in auxiliary bipartite graphs.

There is also an optimal consequence for flexibility, a notion introduced by Dvořák, Norin and Postle [17] which measures to what extent one can force an LL-colouring to agree with predetermined preferred colours. Let LL be a list-assignment of GG. A request is a map rr with domain D⊆V(G)D \subseteq V(G) such that r(v)∈L(v)r(v) \in L(v) for every v∈Dv \in D. The graph GG is ε\varepsilon-flexible with respect to LL if some LL-colouring satisfies at least ε∣D∣\varepsilon|D| requests, for every rr. Moreover, a graph GG is weighted ε\varepsilon-flexible with respect to LL if there exists some probability distribution on the LL-colourings of GG such that for every vertex vv, and every colour xx in its list L(v)L(v), the vertex vv is assigned colour xx with probability at least ε\varepsilon. Clearly ε\varepsilon cannot be larger than 1∣L(v)∣\frac{1}{|L(v)|}, since otherwise the expected value of the number of colours assigned to vv would be larger than 11. Moreover, weighted ε\varepsilon-flexibility implies ε\varepsilon-flexibility [17], as can be seen by computing the expected value of the number of satisfied requests.

Given a list packing for a kk-list-assignment LL of a graph GG, the uniform probability distribution on the kk disjoint LL-colourings shows that GG is weighted 1k\frac{1}{k}-flexible with respect to LL. Therefore Corollary 1.4 implies the next result.

Corollary 1.5. Every triangle-free planar graph is weighted 1/41/4-flexible, and hence 1/41/4-flexible, with respect to every 44-list-assignment. The constant 1/41/4 is best possible in the weighted statement.

In their foundational paper, Dvořák, Norin and Postle asked [17 Problem 5] whether there exists an absolute constant ε>0\varepsilon> 0 such that every triangle-free planar graph is weighted ε\varepsilon-flexible for some ε>0\varepsilon> 0 with respect to every 44-list-assignment. Dvořák, Masařík, Musílek and Pangrác answered this affirmatively [16] via an involved discharging argument and reducible configurations. The parameters in their proof give ε=2−186\varepsilon= 2^{-186}. Our result strengthens their theorem to the largest possible value ε=1/4\varepsilon= 1/4. More substantially, the four colourings may be chosen to form a packing, and the underlying packing theorem extends from list colouring to arbitrary correspondence colouring. For more results on (weighted) flexibility that were obtained independent of the packing perspective, particularly for planar graphs, we refer to [BCK25, DMMP20, CCF+22, BMS22, BB26, DMMP21].

In § 2 we prove Theorem 1.1 via a Key Lemma. The corollaries are proved in § 3. In § 4, we present a Generalized Key Lemma that goes beyond forest decompositions. We expect it to find future applications to more involved graph classes. We finish with a few open problems in § 5.

Proof of the main theorem

The proof of the main theorem relies on the Key Lemma below. For a spanning subgraph J⊆GJ \subseteq G, write G−E(J)G-E(J) for the spanning graph with edge set E(G)∖E(J)E(G) \setminus E(J).

Key Lemma. Let JJ be a spanning subgraph of GG such that G−E(J)G-E(J) is a forest. Then

χc⋆(G)≤2χc⋆(J)\chi^{\star}_{c}(G) \le2\chi^{\star}_{c}(J)

Proof. We first argue that the lists can be split in some suitable way. Fix an integer k≥1k \ge1 and a 2k2k-fold correspondence cover H=(L,H)\mathcal{H}=(L,H) of GG. By exploiting that F:=G−E(J)F:=G-E(J) is a 11-degenerate graph, we shall partition every list L(v)L(v) as the disjoint union of two lists L0(v)L_0(v) and L1(v)L_1(v) of equal size ∣L0(v)∣=∣L1(v)∣=k|L_0(v)|=|L_1(v)|=k, in such a way that for every edge uvuv of FF, every edge of HH between L(u)L(u) and L(v)L(v) is either between L0(u)L_0(u) and L1(v)L_1(v) or between L1(u)L_1(u) and L0(v)L_0(v). In other words, for every uv∈E(F)uv \in E(F), we want that no edge of the matching between L(u)L(u) and L(v)L(v) has both endpoints in L0(u)∪L0(v)L_0(u) \cup L_0(v) or both endpoints in L1(u)∪L1(v)L_1(u) \cup L_1(v).

Root every component of FF. At a root vv, choose an arbitrary equipartition of L(v)L(v). Suppose uu is the parent of vv and the partition of L(u)L(u) is already fixed. If x∈L(v)x \in L(v) is matched, along the edge uvuv, to y∈Li(u)y \in L_i(u), then force xx into L1−i(v)L_{1-i}(v). Since the edges between L(u)L(u) and L(v)L(v) form a matching, at most kk colours of L(v)L(v) are forced into either part. Assign the remaining colours (if there are any) so that both parts have size kk. Proceeding away from the roots gives the desired split of the lists.

Let Hi=H[⋃vLi(v)]\mathcal{H}_i=\mathcal{H}[\bigcup_v L_i(v)] be the cover restricted to part ii. Since no edge of H\mathcal{H} arising from FF has both ends in part ii, it follows that Hi\mathcal{H}_i is a kk-fold cover of JJ. Moreover, every independent transversal of Hi\mathcal{H}_i is automatically an independent transversal of H\mathcal{H}.

Now set k=χc⋆(J)k=\chi^{\star}_{c}(J). Each Hi\mathcal{H}_i has a packing into kk independent transversals, and the packings of H1\mathcal{H}_1 and H2\mathcal{H}_2 together form a packing of the original 2k2k-fold cover of GG. Hence χc⋆(G)≤2k\chi^{\star}_{c}(G)\le2k.

Corollary 2.1. If J⊆GJ\subseteq G is spanning and G−E(J)G-E(J) is the union of rr forests, then χc⋆(G)≤2r⋅χc⋆(J)\chi^{\star}_{c}(G)\le2^r\cdot\chi^{\star}_{c}(J).

Proof. Add the forests one at a time and iteratively apply the Key Lemma.

Proof of Theorem 1.1. Take JJ edge-less in Corollary 2.1.

Proofs of the corollaries

Proof of Corollary 1.2. By the Nash–Williams arboricity theorem [24], arb⁡(G)≤t\operatorname{arb}(G)\le t if and only if every subgraph JJ with at least two vertices satisfies ∣E(J)∣≤t⋅(∣V(J)∣−1)|E(J)|\le t\cdot(|V(J)|-1). If arb⁡(G)≥4\operatorname{arb}(G)\ge4, then some subgraph JJ with n=∣V(J)∣n=|V(J)| and m=∣E(J)∣m=|E(J)| has m>3(n−1)m>3(n-1). This is only possible if n≥7n\ge7, so mad⁡(G)≥2mn≥6−4n≥387\operatorname{mad}(G)\ge\frac{2m}{n}\ge6-\frac{4}{n}\ge\frac{38}{7}. Thus mad⁡(G)<38/7\operatorname{mad}(G)<38/7 implies arb⁡(G)≤3\operatorname{arb}(G)\le3. Similarly, if arb⁡(G)≥3\operatorname{arb}(G)\ge3, then some subgraph has m≥2n−1m\ge2n-1. Then n≥5n\ge5, so $\operatorname{mad}(G)\ge \frac{2m}{n}\ge 4−2n≥1854-\frac{2}{n} \ge\frac{18}{5}. Thus mad⁡(G)<18/5\operatorname{mad}(G) < 18/5 implies arb⁡(G)≤2\operatorname{arb}(G) \le2. Finally, mad⁡(G)<2\operatorname{mad}(G) < 2 implies GG is a forest and thus arb⁡(G)≤1\operatorname{arb}(G) \le1. The three bounds now follow from Theorem 1.1.

Proof of Corollary 1.3. The extremal bounds of Mader [23] give ∣E(J)∣≤3∣V(J)∣−6|E(J)| \le3|V(J)|-6 for every K5K_5-minor-free subgraph JJ with at least three vertices, and ∣E(J)∣≤2∣V(J)∣−3|E(J)| \le2|V(J)|-3 for every K4K_4-minor-free subgraph JJ with at least two vertices. Nash–Williams therefore gives arboricity at most 3 and 2, respectively. A K3K_3-minor-free graph is a forest, and hence has arboricity at most 1. Apply Theorem 1.1.

Proof of Corollary 1.4. Every planar graph is K5K_5-minor-free, so the first assertion follows from Corollary 1.3. If GG is triangle-free and planar, then every subgraph JJ with n≥3n \ge3 vertices has ∣E(J)∣≤2n−4≤2(n−1)|E(J)| \le2n-4 \le2(n-1) by Euler’s formula. The same bound holds for n=2n=2. Hence arb⁡(G)≤2\operatorname{arb}(G) \le2 by Nash–Williams.

Proof of Corollary 1.5. Let LL be a 4-list-assignment of a triangle-free planar graph GG. By Corollary 1.4, the associated correspondence-cover has a packing of four LL-colourings. At every vertex these colourings use each colour in its list exactly once, so the uniform distribution on them assigns every colour probability 1/41/4. Thus GG is weighted 1/41/4-flexible, and hence 1/41/4-flexible. Conversely, for any probability distribution on LL-colourings and any vertex vv, the probabilities of the four colours in L(v)L(v) sum to 1. Therefore no larger uniform lower bound is possible.

Generalized key lemma

The results in this section are not necessary for the main results of the current paper, but we present them with a view to potential future applications to more involved graph classes, via partitions into graphs other than forests. Since forests are 1-degenerate graphs, our Key Lemma is a special case of Corollary 4.5 below. First we need some definitions.

Definition 4.1. The fractional list packing number χℓ∘(G)\chi_\ell^{\circ}(G) of a graph GG is the smallest integer kk such that GG is weighted 1/k1/k-flexible with respect to every kk-fold list-assignment.

Similar to how the notion of weighted 1/k1/k-flexibility can be viewed as a relaxation of a list packing, one can relax a correspondence packing to a fractional correspondence packing.

Definition 4.2. The fractional correspondence packing number χc∘(G)\chi_c^{\circ}(G) of a graph GG is the smallest integer kk such that every kk-fold cover (L,H)(L,H) of GG admits a probability distribution on the independent transversals such that for every vertex vv, every colour in L(v)L(v) appears with probability 1/k1/k.

For background and results on the fractional packing numbers, we refer to [6, 10, 5]. The next definition is new, as far as we are aware. It facilitates a streamlined statement of the Generalized Key Lemma.

Definition 4.3. We define the correspondence splitting number σc(F)\sigma_c(F) of a graph FF as the least positive integer ss such that the following holds for every integer k≥1k \ge1. For every sksk-fold correspondence cover H=(L,H)\mathcal{H}=(L,H) of FF, there are partitions L(v)=L1(v)∪⋯∪Ls(v)L(v)=L_1(v)\cup\cdots\cup L_s(v) of the lists, such that for every vertex vv and every j∈[s]j\in[s] we have ∣Lj(v)∣=k|L_j(v)|=k, and for every edge uv∈E(F)uv\in E(F) and every j∈[s]j\in[s], there is no edge in HH between Lj(u)L_j(u) and Lj(v)L_j(v). The list splitting number σℓ(F)\sigma_\ell(F) of a graph FF is defined analogously; then the conditions only are required to hold for the correspondence covers that arise from an sksk-list assignment.

It is easy to see that σℓ(G)≤σc(G)\sigma_\ell(G) \le\sigma_c(G) and χℓ∘(G)≤χc∘(G)≤χc⋆(G)\chi_\ell^{\circ}(G) \le\chi_c^{\circ}(G) \le\chi_c^{\star}(G) and χℓ(G)≤χℓ∘(G)≤χℓ⋆(G)≤χc⋆(G)≤σc(G)\chi_\ell(G) \le\chi_\ell^{\circ}(G) \le\chi_\ell^{\star}(G) \le\chi_c^{\star}(G) \le\sigma_c(G) for every graph GG.

Generalized Key Lemma. Let JJ be a spanning subgraph of GG. Write F:=G−E(J)F := G - E(J). Then

χc∗(G)≤σc(F)⋅χc∗(J),\chi_c^*(G) \le\sigma_c(F) \cdot\chi_c^*(J),
χc(G)≤σc(F)⋅χc(J),\chi_c(G) \le\sigma_c(F) \cdot\chi_c(J),
χℓ∗(G)≤σℓ(F)⋅χℓ∗(J),\chi_\ell^*(G) \le\sigma_\ell(F) \cdot\chi_\ell^*(J),
χℓ(G)≤σℓ(F)⋅χℓ(J).\chi_\ell(G) \le\sigma_\ell(F) \cdot\chi_\ell(J).

Proof. We will focus on the first inequality, as the other three are proved similarly. Let s:=σc(F)s := \sigma_c(F) and k:=χc∗(J)k := \chi_c^*(J). Take an arbitrary sksk-fold correspondence cover (L,H)(L,H) of GG. By definition of σc(F)\sigma_c(F), there exists a partition of V(H)V(H) into parts P1,P2,…,PsP_1,P_2,\ldots,P_s, such that for every j∈[s]j \in[s] the following holds: for every vertex vv the truncated list Lj(v):=L(v)∩PjL_j(v) := L(v) \cap P_j has size kk, and for every edge uv∈E(F)uv \in E(F) there is no edge between Lj(u)L_j(u) and Lj(v)L_j(v) in HH.

For each j∈[s]j \in[s], the induced subgraph Hj:=H[Pj]H_j := H[P_j] equipped with lists Lj:=(Lj(v))v∈V(G)L_j := (L_j(v))_{v \in V(G)} forms a kk-fold correspondence cover (Lj,Hj)(L_j,H_j) of JJ and thus admits a packing, a partition into kk independent transversals. As no edge of FF corresponds to any edge in HjH_j, these are also independent transversals of (L,H)(L,H). Taking all ss packings together yields an sksk-packing of (L,H)(L,H). Hence χc∗(G)≤s⋅k\chi_c^*(G) \le s \cdot k.

The fractional statement in terms of χc∗\chi_c^* follows identically, by first choosing j∈[s]j \in[s] uniformly at random and then sampling a fractional packing from the cover (Lj,Hj)(L_j,H_j) of JJ. In the second stage (conditional on the value of jj) every vertex of HjH_j is selected with probability 1/k1/k because χc∗(J)=k\chi_c^*(J) = k. Every vertex of HH belongs to exactly one HjH_j, and hence altogether is selected with probability 1s⋅1k=1sk\frac{1}{s} \cdot\frac{1}{k} = \frac{1}{sk}.

The last two inequalities in terms of χℓ∗\chi_\ell^* and χℓ\chi_\ell also follow via the same proof, by restricting to the correspondence covers that arise from list-assignments.

The next lemma allows to convert the Generalized Key Lemma into a concrete special case, allowing decompositions into graphs with bounded degeneracy. By definition, a graph is dd-degenerate if there exists an ordering of the vertices such that every vertex has at most dd neighbours earlier in the ordering.

Lemma 4.4. For every dd-degenerate graph FF, we have σc(F)≤2d\sigma_c(F) \le2d.

Proof. Fix an integer k≥1k \ge1, and let H=(L,H)\mathcal{H} = (L,H) be an arbitrary 2dk2dk-fold correspondence cover of FF. We need to show that for every v∈V(F)v \in V(F) one can partition the list L(v)L(v) into 2d2d disjoint sublists L1(v),L2(v),…,L2d(v)L_1(v),L_2(v),\ldots,L_{2d}(v), each of size kk, in such a way that for every uv∈E(F)uv \in E(F) and every j∈[2d]j \in[2d], there is no edge between Lj(u)L_j(u) and Lj(v)L_j(v) in HH.

Choose a degeneracy ordering v1,…,vnv_1,\ldots,v_n of FF, so that every vsv_s has at most dd neighbours among v1,…,vs−1v_1,\ldots,v_{s-1}. We construct the partitions in this order. Suppose that v=vsv = v_s is being processed, and let u1,…,uru_1,\ldots,u_r be its earlier neighbours in FF. Their partitions have already been fixed. We now need to construct L1(v),…,L2d(v)L_1(v),\ldots,L_{2d}(v).

For a colour x∈L(v)x \in L(v) and an index j∈[2d]j \in[2d], say that jj is forbidden for xx if xx has a neighbour in ⋃i∈[r]Lj(ui)\bigcup_{i \in[r]} L_j(u_i), in the cover graph HH. Otherwise jj is allowed for xx.

Since the edges between L(ui)L(u_i) and L(v)L(v) form a matching, each earlier neighbour uiu_i forbids at most one index jj for a fixed colour xx. Hence every x∈L(v)x \in L(v) has at most dd forbidden indices, and consequently at least dd allowed indices. Conversely, fix j∈[2d]j \in[2d]. For each earlier neighbour uiu_i, the sublist Lj(ui)L_j(u_i) contains kk colours, so at most kk colours of L(v)L(v) are matched to colours in Lj(ui)L_j(u_i). Thus at most rk≤dkrk \le dk colours of L(v)L(v) are forbidden to appear in Lj(v)L_j(v).

We now use Hall’s theorem. Construct an auxiliary bipartite graph BB whose left part is the list of colours L(v)L(v), and whose right part consists of kk copies j1,…,jkj^1,\ldots,j^k of every index j∈[2d]j \in[2d]. Join x∈L(v)x \in L(v) to every copy of jj precisely when jj is allowed for xx. Note that both sides of BB have size 2dk2dk. We verify Hall’s condition. Let S⊆L(v)S \subseteq L(v). If ∣S∣≤dk|S| \le dk, then every x∈Sx \in S is adjacent to all kk copies of at least dd indices. Hence ∣NB(S)∣≥dk≥∣S∣|N_B(S)| \ge dk \ge|S|. Now suppose instead that ∣S∣>dk|S| > dk. Fix j∈[2d]j \in[2d]. At most dkdk colours of L(v)L(v) are forbidden to appear in LjL_j, so some colour of SS is allowed in LjL_j. Hence all kk copies j1,…,jkj^1,\ldots,j^k are neighbours of SS. Since this holds for every j∈[2d]j \in[2d], it follows that NB(S)N_B(S) is the entire right side of BB, so ∣NB(S)∣=2dk≥∣S∣|N_B(S)| = 2dk \ge|S|. Thus we may apply Hall’s matching theorem: BB has a perfect matching.

We convert the perfect matching to a choice of sublists of L(v)L(v). Assign colour x∈L(v)x \in L(v) to sublist Lj(v)L_j(v) if and only if xx is matched in BB to one of the kk copies of jj. Since jj is allowed for xx, this does not create any undesirable edge between Lj(u)L_j(u) and Lj(v)L_j(v) for any edge uv∈E(F)uv \in E(F). Moreover, since each of the kk copies of jj is matched, this gives ∣Lj(v)∣=k|L_j(v)| = k for every jj.

Corollary 4.5. Let JJ be a spanning subgraph of a graph GG such that F:=G−E(J)F := G - E(J) is dd-degenerate for some d≥1d \ge1. Then χc∗(G)≤2d⋅χc∗(J)\chi_c^*(G) \le2d \cdot\chi_c^*(J) and χc∗(G)≤2d⋅χc∗(J)\chi_c^*(G) \le2d \cdot\chi_c^*(J).

Proof. Apply the Generalized Key Lemma to the bound in Lemma 4.4.

Remark 4.6.

  • Taking JJ the spanning edgeless graph in Corollary 4.5, we recover the result from [7] that χc∗(G)\chi_c^*(G) is at most twice the degeneracy of GG. This is sharp due to large complete bipartite graphs.

  • Taking JJ a spanning forest (which is 1-degenerate) in Corollary 4.5, we recover the Key Lemma.

  • Taking k=1k = 1 in the definition of σc(F)\sigma_c(F) yields χc∗(F)≤σc(F)\chi_c^*(F) \le\sigma_c(F). It would be interesting to understand under which conditions there is equality, χc∗(F)=σc(F)\chi_c^*(F) = \sigma_c(F). Let F\mathcal{F} denote the class of such graphs. Then for every spanning subgraph JJ of GG such that G−E(J)∈FG - E(J) \in\mathcal{F}, the following attractive product inequality holds:

χc∗(G)≤χc∗(G−E(J))⋅χc∗(J).\chi_c^*(G) \le\chi_c^*(G - E(J)) \cdot\chi_c^*(J).

We end this section with a refined variant of the Generalized Key Lemma. Given a list assignment LL and positive integer kk, a kk-fold LL-colouring is a mapping ϕ\phi such that ϕ(v)\phi(v) is a size kk-subset of L(v)L(v) for each vertex vv, and ϕ(u)∩ϕ(v)=∅\phi(u) \cap\phi(v) = \varnothing for each edge uvuv. For a positive integer ss, we say a graph GG is list (sk,k)(sk,k)-packable if for any sksk-fold assignment LL, there are kk-fold LL-colourings ϕ1,…,ϕs\phi_1,\ldots,\phi_s such that {ϕ1(v),…,ϕs(v)}\{\phi_1(v),\ldots,\phi_s(v)\} is a partition of L(v)L(v) for each vertex vv. The concept of correspondence-(sk,k)(sk,k)-packable is defined similarly. By the proof of the Generalized Key Lemma, it follows that if a graph GG decomposes into G1∪G2G_1 \cup G_2, and G1G_1 is (sk,k)(sk,k)-packable and G2G_2 is kk-packable, then GG is sksk-packable.

One might even hope that G1G_1 ss-packable and G2G_2 kk-packable implies that GG is sksk-packable. To achieve that, a natural conjecture would be that if GG is ss-packable, then GG is (sk,k)(sk,k)-packable for any positive integer kk. However, that is probably too optimistic because a closely related statement for list colourings was false: Erdős, Rubin and Taylor conjectured Erdős, Rubin and Taylor [19] that if GG is (a,b)(a,b)-choosable, then GG is (ak,bk)(ak,bk)-choosable for any positive integer kk, and this has been disproved [14].

Concluding remarks

We conclude with open problems. Some are achievable with assistance from current AI models. However, the challenge is to obtain an elegant humanly readable proof.

(1) What is the optimal upper bound on χc∗(G)\chi_c^*(G) for graphs GG with arboricity 3? Is it 6, 7 or 8?

(2) From [10], it is known that χc∗(G)≤3\chi_c^*(G) \le3 for planar graphs of girth ≥6\ge6, while there are triangle-free planar graphs with χc∗(G)=4\chi_c^*(G) = 4. Do all planar graphs of girth 5 satisfy χc∗(G)≤3\chi_c^*(G) \le3? For the integral packing numbers this is false: there exist planar graphs GG of arbitrarily large girth with χℓ∗(G)=χc∗(G)=4\chi_\ell^*(G) = \chi_c^*(G) = 4.

(3) In line with Remark 4.6, what other graph decompositions lead to good upper bounds on the various packing numbers? Is there any graph FF for which σc(F)≠χc∗(F)\sigma_c(F) \ne\chi_c^*(F), or σℓ(F)≠χℓ∗(F)\sigma_\ell(F) \ne\chi_\ell^*(F)?

(4) Regarding planar graphs, the main remaining open problem is to determine the optimal upper bound on χℓ∗(G)\chi_\ell^*(G) or χc∗(G)\chi_c^*(G) without any girth constraints. In upcoming work [4], a planar graph with correspondence packing number 6 is presented. There are now three independent proofs that χc∗(G)≤8\chi_c^*(G) \le8 for all planar graphs, the other two proofs appearing in [10, 12]. An obstruction for the decompositions presented in the current paper is that they involve (iterated applications of) bounds of the form σ⋅χc∗(J)\sigma\cdot\chi_c^*(J) for some integer σ≥2\sigma\ge2 and spanning subgraph JJ. Since the only graphs with correspondence packing number <4< 4 are forests, this cannot achieve anything better than 2⋅4=82 \cdot4 = 8 for planar graphs.

(5) Graphs with maximum average degree <6< 6 have [10] correspondence packing number ≤8\le8. Not every such graph can be edge-partitioned into at most three forests, so the current approach fails to recover that result in an easy way. It is however interesting to note that every such graph can be partitioned into at most one forest and two pseudoforests. Here, a pseudo-forest is a graph such that every connected component has at most one cycle. Can this lead to an elegant alternative proof?

(6) For k∈{2,4,5,8}k \in\{2,4,5,8\}, we now have a reasonably good picture of the optimal conditions on maximum average degree that ensure χc∗(G)≤k\chi_c^*(G) \le k. For k∈{2,4,5}k \in\{2,4,5\} the bounds are sharp. What about k∈{6,7}k \in\{6,7\}? We reiterate a question from [10]: does mad⁡(G)<k−1\operatorname{mad}(G) < k - 1 imply χc∗(G)≤k\chi_c^*(G) \le k? We conjecture that this is true for k=6k = 6.

Disclosure and background In conversation with a closed-weight AI model about proving χc∗(G)≤4\chi_c^*(G) \le4 for every triangle-free planar graph GG, one of the suggestions of the model was to use that they admit a decomposition into two forests. This eventually led to a direct but obscure proof by induction for triangle-free planar graphs, based on binary sequences associated with the vertices. The authors isolated the key step, formulated the Key Lemma, and from there obtained the other corollaries and the Generalized Key Lemma.

References

  1. [4]Wouter Cames van Batenburg. A planar graph with correspondence packing number 6 (in preparation). ↑8
  2. [5]Stijn Cambie and Wouter Cames van Batenburg (2026). Fractional list packing for layered graphs. Journal of Graph Theory 113(1), 19–37. ↑2, 5DOI
  3. [6]Stijn Cambie, Wouter Cames van Batenburg, Ewan Davies, and Ross J. Kang (2024). List packing number of bounded degree graphs. Combinatorics, Probability and Computing 33(6), 807–828. ↑2, 5DOI
  4. [7]Stijn Cambie, Wouter Cames van Batenburg, Ewan Davies, and Ross J. Kang (2024). Packing list-colourings. Random Structures & Algorithms 64(1), 62–93. ↑1, 2, 7DOI
  5. [9]Wouter Cames van Batenburg, Daniel W. Cranston, and František Kardoš (2026). Disjoint correspondence colorings for K₅-minor-free graphs. ↑2, 3arxiv.org/abs/2602.16692
  6. [10]Stijn Cambie, Wouter Cames van Batenburg, and Xuding Zhu (2023). Disjoint list-colorings for planar graphs. ↑1, 2, 3, 5, 8arxiv.org/abs/2312.17233
  7. [11]Stijn Cambie and Rimma Hämäläinen (2025). Packing colourings in complete bipartite graphs and the inverse problem for correspondence packing. Journal of Graph Theory 109(1), 52–61. ↑2arxiv.org/abs/2303.01944
  8. [12]Daniel W. Cranston and Landon Smith-Roberge (2025). List packing and correspondence packing of planar graphs. Journal of Graph Theory 109(3), 339–352. ↑2, 3, 8arxiv.org/abs/2401.01332
  9. [13]Debsoumya Chakraborti and Tuan Tran (2025). Approximate packing of independent transversals in locally sparse graphs. Journal of Combinatorial Theory, Series B 175, 187–212. ↑2arxiv.org/abs/2402.02815
  10. [14]Zdeněk Dvořák, Xuding Hu, and Jean-Sébastien Sereni (2019). A 4-choosable graph that is not (8 : 2)-choosable. Advances in Combinatorics (5), 9. ↑7DOI
  11. [16]Zdeněk Dvořák, Tomáš Masarík, Jan Musílek, and Ondřej Pangrác (2021). Flexibility of triangle-free planar graphs. Journal of Graph Theory 96(4), 619–641. ↑3, 4DOI
  12. [17]Zdeněk Dvořák, Sergey Norin, and Luke Postle (2019). List coloring with requests. Journal of Graph Theory 92(3), 191–206. ↑3
  13. [18]Zdeněk Dvořák and Luke Postle (2018). Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8. Journal of Combinatorial Theory, Series B 129, 38–54. ↑1arxiv.org/abs/1508.03437
  14. [19]Paul Erdős, Arthur L. Rubin, and Herbert Taylor (1980). Choosability in graphs. Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, vol. 26, 125–157 (Arcata, California). ↑7
  15. [20]Hemanshu Kaul and Jeffrey Mudrock (2025). Counting packings of list-colorings of graphs. Enumerative Combinatorics and Applications 5(3). ↑2arxiv.org/abs/2401.11025
  16. [21]Hemanshu Kaul, Rogers Mathew, Jeffrey A. Mudrock, and Michael J. Pelsmajer (2024). Flexible list colorings: maximizing the number of requests satisfied. Journal of Graph Theory 106(4), 887–906. ↑2arxiv.org/abs/2211.09048
  17. [22]Masaki Kashima, Shun-ichi Maezawa, and Xuding Zhu (2026). List packing of graphs with bounded tree-width. ↑2arxiv.org/abs/2603.26187
  18. [23]Wolfgang Mader (1968). Homomorphiesätze für graphen. Mathematische Annalen 178, 154–168. ↑5
  19. [24]C. St. J. A. Nash-Williams (1964). Decomposition of finite graphs into forests. Journal of the London Mathematical Society 39(1), 12–12. ↑2, 4
  20. [25]Carsten Thomassen (1994). Every planar graph is 5-choosable. Journal of Combinatorial Theory, Series B 62(1), 180–181. ↑1DOI

Paper details

vlnc:W_93daccu5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

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

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents