WorksMathematics
List packing for graphs with small arboricity
Abstract
We prove that every graph whose edge set is the union of forests has list packing number at most . This means that for all and every list-assignment with lists of size , the graph admits disjoint proper -colourings. While for large this bound is far from optimal, for it is sharp. As a direct corollary of the case , we obtain that every triangle-free planar graph has list packing number at most , 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 , we obtain a short alternative proof that every -minor-free (and hence every planar) graph has list-packing number at most , 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 -list-assignment assigns to every vertex a private set of allowed colours, and an -colouring is a proper vertex-colouring such that for every vertex . The smallest such that every -list-assignment of admits an -colouring is the list chromatic number . 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 -packing of is a collection of pairwise disjoint -colourings , meaning that for every distinct and . As a consequence, these colourings partition every list . The list packing number of is the smallest integer such that every -list-assignment of admits an -packing. The most basic but still completely open problem in this area is whether for some absolute constant .
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 is a pair , where is a graph, the sets partition , every is a clique, and, for each edge , the edges of between and form a matching . If , then there is no edge between and . The cover is -fold if for every . An -colouring is an independent transversal of , meaning an independent set of that intersects every list . A -packing is a collection of pairwise disjoint independent transversals. Thus, an -packing partitions into independent transversals. The correspondence packing number is the least integer such that every -fold correspondence-cover of has a packing. Every list-assignment has an associated correspondence-cover, so for every graph .
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 of a graph is the least number of forests whose edge sets partition . Our main result gives a direct connection between this classical density parameter and correspondence packing.
Theorem 1.1. Every graph satisfies
As we will see later, Theorem 1.1 is sharp for . For , the optimal bound could be 6, 7, or 8. For , a simple degeneracy argument already supplies something better. Indeed, the degeneracy of is at most and as proved in [7], twice degeneracy is a sharp upper bound on . 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 is defined as the average degree maximized over all subgraphs of . The Nash–Williams arboricity theorem [24] relates arboricity with maximum average degree, turning Theorem 1.1 into a density bound
Corollary 1.2.
The bound 8 was already known under the weaker condition , but with a long proof that required a computer-assisted preprocessing step to count certain tuples of small permutations [10]. Our condition is sharp due to the complete graph on 5 vertices with one edge removed, and improves the previous best-known [10, 12] condition . The result under condition is trivial, but it allows us to emphasize a curious gap [11]: there exists no graph with . For completeness, we also mention the result from [10, 12] that whenever , which is sharp because . Our second corollary recovers results from [10] for graphs that exclude a small clique minor.
Corollary 1.3.
The bounds for -minor-free and -minor-free graphs are optimal. Recent work [9] shows that there exist -minor-free graphs with correspondence packing number , and every -fold correspondence-cover of every -minor-free graph admits three pairwise disjoint colourings, but remains conjectural. Our third corollary is perhaps the most appealing.
Corollary 1.4.
For triangle-free planar graphs, Corollary 1.4 improves the previous upper bound [10, 12] from to . This was open even for bipartite planar graphs and it is sharp in a strong sense. For instance, every cycle has correspondence packing number , and due to a construction in [10], there exist planar graphs of arbitrarily large girth with list packing number . The result for general planar graphs recovers the known bound 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 -colouring to agree with predetermined preferred colours. Let be a list-assignment of . A request is a map with domain such that for every . The graph is -flexible with respect to if some -colouring satisfies at least requests, for every . Moreover, a graph is weighted -flexible with respect to if there exists some probability distribution on the -colourings of such that for every vertex , and every colour in its list , the vertex is assigned colour with probability at least . Clearly cannot be larger than , since otherwise the expected value of the number of colours assigned to would be larger than . Moreover, weighted -flexibility implies -flexibility [17], as can be seen by computing the expected value of the number of satisfied requests.
Given a list packing for a -list-assignment of a graph , the uniform probability distribution on the disjoint -colourings shows that is weighted -flexible with respect to . Therefore Corollary 1.4 implies the next result.
Corollary 1.5. Every triangle-free planar graph is weighted -flexible, and hence -flexible, with respect to every -list-assignment. The constant 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 such that every triangle-free planar graph is weighted -flexible for some with respect to every -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 . Our result strengthens their theorem to the largest possible value . 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 , write for the spanning graph with edge set .
Key Lemma. Let be a spanning subgraph of such that is a forest. Then
Proof. We first argue that the lists can be split in some suitable way. Fix an integer and a -fold correspondence cover of . By exploiting that is a -degenerate graph, we shall partition every list as the disjoint union of two lists and of equal size , in such a way that for every edge of , every edge of between and is either between and or between and . In other words, for every , we want that no edge of the matching between and has both endpoints in or both endpoints in .
Root every component of . At a root , choose an arbitrary equipartition of . Suppose is the parent of and the partition of is already fixed. If is matched, along the edge , to , then force into . Since the edges between and form a matching, at most colours of are forced into either part. Assign the remaining colours (if there are any) so that both parts have size . Proceeding away from the roots gives the desired split of the lists.
Let be the cover restricted to part . Since no edge of arising from has both ends in part , it follows that is a -fold cover of . Moreover, every independent transversal of is automatically an independent transversal of .
Now set . Each has a packing into independent transversals, and the packings of and together form a packing of the original -fold cover of . Hence .
Corollary 2.1. If is spanning and is the union of forests, then .
Proof. Add the forests one at a time and iteratively apply the Key Lemma.
Proof of Theorem 1.1. Take edge-less in Corollary 2.1.
Proofs of the corollaries
Proof of Corollary 1.2. By the Nash–Williams arboricity theorem [24], if and only if every subgraph with at least two vertices satisfies . If , then some subgraph with and has . This is only possible if , so . Thus implies . Similarly, if , then some subgraph has . Then , so $\operatorname{mad}(G)\ge \frac{2m}{n}\ge . Thus implies . Finally, implies is a forest and thus . The three bounds now follow from Theorem 1.1.
Proof of Corollary 1.3. The extremal bounds of Mader [23] give for every -minor-free subgraph with at least three vertices, and for every -minor-free subgraph with at least two vertices. Nash–Williams therefore gives arboricity at most 3 and 2, respectively. A -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 -minor-free, so the first assertion follows from Corollary 1.3. If is triangle-free and planar, then every subgraph with vertices has by Euler’s formula. The same bound holds for . Hence by Nash–Williams.
Proof of Corollary 1.5. Let be a 4-list-assignment of a triangle-free planar graph . By Corollary 1.4, the associated correspondence-cover has a packing of four -colourings. At every vertex these colourings use each colour in its list exactly once, so the uniform distribution on them assigns every colour probability . Thus is weighted -flexible, and hence -flexible. Conversely, for any probability distribution on -colourings and any vertex , the probabilities of the four colours in 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 of a graph is the smallest integer such that is weighted -flexible with respect to every -fold list-assignment.
Similar to how the notion of weighted -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 of a graph is the smallest integer such that every -fold cover of admits a probability distribution on the independent transversals such that for every vertex , every colour in appears with probability .
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 of a graph as the least positive integer such that the following holds for every integer . For every -fold correspondence cover of , there are partitions of the lists, such that for every vertex and every we have , and for every edge and every , there is no edge in between and . The list splitting number of a graph is defined analogously; then the conditions only are required to hold for the correspondence covers that arise from an -list assignment.
It is easy to see that and and for every graph .
Generalized Key Lemma. Let be a spanning subgraph of . Write . Then
Proof. We will focus on the first inequality, as the other three are proved similarly. Let and . Take an arbitrary -fold correspondence cover of . By definition of , there exists a partition of into parts , such that for every the following holds: for every vertex the truncated list has size , and for every edge there is no edge between and in .
For each , the induced subgraph equipped with lists forms a -fold correspondence cover of and thus admits a packing, a partition into independent transversals. As no edge of corresponds to any edge in , these are also independent transversals of . Taking all packings together yields an -packing of . Hence .
The fractional statement in terms of follows identically, by first choosing uniformly at random and then sampling a fractional packing from the cover of . In the second stage (conditional on the value of ) every vertex of is selected with probability because . Every vertex of belongs to exactly one , and hence altogether is selected with probability .
The last two inequalities in terms of and 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 -degenerate if there exists an ordering of the vertices such that every vertex has at most neighbours earlier in the ordering.
Lemma 4.4. For every -degenerate graph , we have .
Proof. Fix an integer , and let be an arbitrary -fold correspondence cover of . We need to show that for every one can partition the list into disjoint sublists , each of size , in such a way that for every and every , there is no edge between and in .
Choose a degeneracy ordering of , so that every has at most neighbours among . We construct the partitions in this order. Suppose that is being processed, and let be its earlier neighbours in . Their partitions have already been fixed. We now need to construct .
For a colour and an index , say that is forbidden for if has a neighbour in , in the cover graph . Otherwise is allowed for .
Since the edges between and form a matching, each earlier neighbour forbids at most one index for a fixed colour . Hence every has at most forbidden indices, and consequently at least allowed indices. Conversely, fix . For each earlier neighbour , the sublist contains colours, so at most colours of are matched to colours in . Thus at most colours of are forbidden to appear in .
We now use Hall’s theorem. Construct an auxiliary bipartite graph whose left part is the list of colours , and whose right part consists of copies of every index . Join to every copy of precisely when is allowed for . Note that both sides of have size . We verify Hall’s condition. Let . If , then every is adjacent to all copies of at least indices. Hence . Now suppose instead that . Fix . At most colours of are forbidden to appear in , so some colour of is allowed in . Hence all copies are neighbours of . Since this holds for every , it follows that is the entire right side of , so . Thus we may apply Hall’s matching theorem: has a perfect matching.
We convert the perfect matching to a choice of sublists of . Assign colour to sublist if and only if is matched in to one of the copies of . Since is allowed for , this does not create any undesirable edge between and for any edge . Moreover, since each of the copies of is matched, this gives for every .
Corollary 4.5. Let be a spanning subgraph of a graph such that is -degenerate for some . Then and .
Proof. Apply the Generalized Key Lemma to the bound in Lemma 4.4.
Remark 4.6.
Taking the spanning edgeless graph in Corollary 4.5, we recover the result from [7] that is at most twice the degeneracy of . This is sharp due to large complete bipartite graphs.
Taking a spanning forest (which is 1-degenerate) in Corollary 4.5, we recover the Key Lemma.
Taking in the definition of yields . It would be interesting to understand under which conditions there is equality, . Let denote the class of such graphs. Then for every spanning subgraph of such that , the following attractive product inequality holds:
We end this section with a refined variant of the Generalized Key Lemma. Given a list assignment and positive integer , a -fold -colouring is a mapping such that is a size -subset of for each vertex , and for each edge . For a positive integer , we say a graph is list -packable if for any -fold assignment , there are -fold -colourings such that is a partition of for each vertex . The concept of correspondence--packable is defined similarly. By the proof of the Generalized Key Lemma, it follows that if a graph decomposes into , and is -packable and is -packable, then is -packable.
One might even hope that -packable and -packable implies that is -packable. To achieve that, a natural conjecture would be that if is -packable, then is -packable for any positive integer . 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 is -choosable, then is -choosable for any positive integer , 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 for graphs with arboricity 3? Is it 6, 7 or 8?
(2) From [10], it is known that for planar graphs of girth , while there are triangle-free planar graphs with . Do all planar graphs of girth 5 satisfy ? For the integral packing numbers this is false: there exist planar graphs of arbitrarily large girth with .
(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 for which , or ?
(4) Regarding planar graphs, the main remaining open problem is to determine the optimal upper bound on or 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 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 for some integer and spanning subgraph . Since the only graphs with correspondence packing number are forests, this cannot achieve anything better than for planar graphs.
(5) Graphs with maximum average degree have [10] correspondence packing number . 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 , we now have a reasonably good picture of the optimal conditions on maximum average degree that ensure . For the bounds are sharp. What about ? We reiterate a question from [10]: does imply ? We conjecture that this is true for .
Disclosure and background In conversation with a closed-weight AI model about proving for every triangle-free planar graph , 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
- [4]Wouter Cames van Batenburg. A planar graph with correspondence packing number 6 (in preparation). ↑8
- [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
- [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
- [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
- [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
- [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
- [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
- [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
- [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
- [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
- [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
- [17]Zdeněk Dvořák, Sergey Norin, and Luke Postle (2019). List coloring with requests. Journal of Graph Theory 92(3), 191–206. ↑3
- [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
- [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
- [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
- [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
- [22]Masaki Kashima, Shun-ichi Maezawa, and Xuding Zhu (2026). List packing of graphs with bounded tree-width. ↑2arxiv.org/abs/2603.26187
- [23]Wolfgang Mader (1968). Homomorphiesätze für graphen. Mathematische Annalen 178, 154–168. ↑5
- [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
- [25]Carsten Thomassen (1994). Every planar graph is 5-choosable. Journal of Combinatorial Theory, Series B 62(1), 180–181. ↑1DOI