TOPICS
Search

List Packing Number


The list packing number chi_l^*(G) of a finite simple graph G is the least positive integer k such that every assignment of a k-element color list L(v) to each graph vertex admits k proper list colorings c_1,...,c_k with c_i(v)!=c_j(v) whenever i!=j (Cambie et al. 2024). Thus the colorings collectively use each available color exactly once at each graph vertex. The correspondence packing number chi_c^*(G) imposes the analogous requirement on every k-fold correspondence coloring cover. It requires a partition of the cover into k independent vertex sets, each meeting every color list exactly once. In particular, chi_l(G)<=chi_l^*(G)<=chi_c^*(G), where chi_l(G) is the choice number.

Cambie et al. (2026) proved

 chi_c^*(G)<=2^(arb(G)),

where arb(G) is the arboricity. The bound is sharp for arboricity 1 and 2. It gives a bound of 4 for every triangle-free planar graph, and 8 for every K_5-minor-free graph. For graphs with maximum average degree less than 18/5, the correspondence packing number is at most 4, and this density condition is sharp.

For a triangle-free planar graph with lists of four colors, the four disjoint colorings give a statistical distribution on proper list colorings in which every available color at every graph vertex is used with probability 1/4. Consequently, arbitrary preferred colors can be satisfied simultaneously at at least a quarter of the requested vertices, including the corresponding weighted version (Cambie et al. 2026). The authors report that an AI suggestion to use a decomposition into two forests initiated the proof approach.

Zhang (2026) proves a bound in terms of the maximum number D of forbidden partners of a single color in a correspondence coloring cover of a finite bipartite graph. For each integer D>=[e^(20)], every such cover with

 k=[D/(lnD-2lnlnD-6)]

colors at each graph vertex admits a partition into k independent transversals, hence a full correspondence packing. Thus k=(1+o(1))D/lnD suffices, without bounding the degree of the underlying bipartite graph. Another sufficient condition for lists of size k>=[e^(10)] is that every color have at most k(lnk-lnlnk-6) forbidden partners. Zhang (2026) attributes the displayed explicit choice of k, following his asymptotic proof, to a suggestion by GPT-6.1 Sol.


See also

Arboricity, Choice Number, Correspondence Coloring, List Coloring

Explore with Wolfram|Alpha

References

Cambie, S.; Cames van Batenburg, W.; Davies, E.; and Kang, R. J. "Packing List-Colorings." Random Struct. Algor. 64, 62-93, 2024. https://doi.org/10.1002/rsa.21181.Cambie, S.; Cames van Batenburg, W.; and Zhu, X. "List Packing for Graphs with Small Arboricity." 18 Nov 2026. https://arxiv.org/abs/2611.24832v1.Zhang, X. "A Proof of a Conjecture on Bipartite Correspondence Packing." 16 Nov 2026. https://arxiv.org/abs/2611.20504v1.

Cite this as:

Weisstein, Eric W. "List Packing Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ListPackingNumber.html

Subject classifications