Cambie–Cranston list-packing conjecture

For a graph $G$ , let $\chi_{\ell}(G)$ denote its list-chromatic number and let $\chi_{\ell}^*(G)$ denote its list packing number, the least $k$ such that every $k$ -assignment admits a proper $L$ -packing of size $k$ . Cambie–Cranston's conjecture. There exists an absolute constant $C>0$ such that, for every graph $G$ ,

\chi_{\ell}^*(G)\leq C\cdot\chi_{\ell}(G).

This conjecture, cited from Cambie et al., would show that list packing and list coloring are comparable up to a universal multiplicative constant; the source excerpt gives no resolution evidence.

References

Primary source

Hemanshu Kaul, Rogers Mathew, Jeffrey A. Mudrock and Michael J. Pelsmajer, “Flexible list colorings: Maximizing the number of requests satisfied”, arXiv:2211.09048 (2024).

2 weeks ago

This conjecture first appeared as Conjecture 1 in https://doi.org/10.1002/rsa.21181, a paper by Cambie, Cames van Batenburg, Davies and Kang.

I have no idea why this website calls it the Cambie-Cranston conjecture. Daniel Cranston has co-authored two papers on the list packing number of planar graphs, but not about this conjecture.
Green Fruit 1 week ago

Progress summary

Refreshed 1 week ago

Claimed progress

No proof or counterexample has been found publicly; only results for special classes of graphs and related counting questions are known.

The conjecture asks whether list packing and list coloring are always within a universal constant factor. The broader linear-comparability question is explicitly recorded as open, with no source reporting a proof or counterexample for the stated conjecture.

Known results

For planar graphs, $\chi_{\ell}^*(G)\leq 8$ ; for girth at least $4$ , $\chi_{\ell}^*(G)\leq 5$ ; and for girth at least $5$ , $\chi_{\ell}^*(G)\leq 4$ (January 2024).
For planar graphs, triangle-free planar graphs, and planar graphs of girth at least $5$ , corresponding counting results strengthen these restricted-family bounds.
For a graph with $n$ vertices and $m$ edges, list-packing and ordinary packing functions agree when $q\geq \frac{nk(k-1)}{2}+mk-1$ ; trees satisfy equality when $k=q$ .

January 2024–2024 partial progress

The planar results advance a problem attributed to Cambie, Cames van Batenburg, Davies, and Kang, but do not establish a universal constant. A later survey records the sharper unresolved targets $\chi_{\ell}^*(G)>\chi_{\ell}(G)+1$ for some graph and $\chi_{\ell}^*(G)\leq 2\chi_{\ell}(G)$ for every graph.

Current status (as of August 2026): The universal-constant conjecture remains open; restricted planar-family bounds and related counting results are known, but no proof or counterexample has been reported.

Sources

No solutions have been posted yet.