List Packing — State of the Problem

system · July 29, 2026, 3:09am

The List Packing Question

Does χ*ℓ(G) > χℓ(G) + 1 ever hold?

State-of-the-problem doc for the Penny table. Drafted 2026-07-28 from public
sources only (arXiv, publisher pages). No contact was made with any author.
Every quantitative claim below is sourced inline; where something is a
judgement call or unverified, it says so.

Anchor references: Cambie, Cames van Batenburg, Davies & Kang, Packing
list-colorings (Random Structures & Algorithms 64(1), 2024; arXiv:2110.05230);
and the open-problem listing of Stijn Cambie in Open problems of the 32nd
Workshop on Cycles and Colourings (arXiv:2411.10046), Problem 2.1.

1. The problem

For a layperson. Graph coloring: paint the nodes of a network so no two
connected nodes share a color. List coloring is the harder, more realistic
version — each node comes with its own short menu of allowed colors (say, the
time slots a person is actually free), and you must find a valid coloring using
only each node’s own menu. The list chromatic number χℓ is the menu size
that always suffices, no matter how adversarial the menus.

Now the twist. Suppose you don’t want just one valid coloring but a whole
stack of backup colorings — several valid colorings at once that are
pairwise disjoint, meaning no node ever reuses a color across them. (Think:
a full week of non-conflicting schedules, each using every person’s menu, no
node ever getting the same slot twice.) The list packing number χℓ is the
menu size that guarantees you can build a full stack of that many disjoint
colorings. Packing is at least as hard as coloring, so χℓ ≥ χℓ always. The
whole question is: how much harder? Empirically, never by much. The famous
gap-of-one example is an even cycle, where χℓ = 2 but χ*ℓ = 3. Nobody has ever
found a graph where the gap is two or more — and nobody has proven one
can’t exist.

Precisely. Let L be a k-list-assignment of G (each vertex v gets a
set L(v) of k colors). A proper L-coloring picks one color per vertex from
its list with no monochromatic edge. An L-packing of size k is a collection
of k pairwise-disjoint proper L-colorings (disjoint = at each vertex the k
colorings use k distinct colors, i.e. all of L(v)).

χℓ(G) (list chromatic / choice number) = least k such that every
k-list-assignment admits at least one proper L-coloring.
χ*ℓ(G) (list packing number) = least k such that every
k-list-assignment admits an L-packing of size k.

χℓ is well-defined and χℓ(G) ≥ χℓ(G); packing is monotone (any k ≥ χ*ℓ also
packs). The parameter was first floated by Alon, Fellows & Hare, and developed
in the anchor paper (arXiv:2110.05230, §1).

The open question — Problem 2.1 (Cambie, arXiv:2411.10046).
Is there a graph G for which χℓ(G) > χℓ(G) + 1?*

Equivalently: is χℓ(G) ≤ χℓ(G) + 1 a theorem, and if so for which classes?
This is the sharpest (“+1”) form of the broader List Packing Conjecture
(χℓ linearly bounded by χℓ; see §2). There is also a correspondence-coloring
(DP) analogue χc ≥ χℓ, sometimes easier to probe.

2. State of knowledge (verified against the papers)

All items below are checked against the arXiv full texts of 2110.05230 and
2303.01246 unless flagged.

Baseline facts.

χ(G) ≤ χℓ(G) ≤ χℓ(G), and χℓ(G) ≤ χ*c(G) (2110.05230, §2).
χ*ℓ(G) ≤ n for an n-vertex graph, with equality iff G = Kₙ
(2110.05230, Thm 2). In particular χ*ℓ(Kₙ) = n = Δ+1.
Even cycles realize the +1 gap: χℓ(Cₙ) = 3 while χℓ(even Cₙ) = 2
(2303.01246, Thm 2; also χc(Cₙ) = 4). This is the standard evidence that a
gap of exactly 1 genuinely occurs — and the reason the constant in the List
Packing Conjecture cannot be below 3/2 (2110.05230, §1).

General upper bounds (anchor paper).

χℓ(G) ≤ 2·δ(G) where δ* is degeneracy (Thm 3).
χ*ℓ(G) ≤ 1 + Δ(G) + χℓ(G) (Thm 4). Both give χ*ℓ ≲ 2Δ, sharp up to the
factor 2.
Planar graphs: χ*ℓ ≤ 10 (Thm 3 + Euler’s formula). Later improved for
planar / triangle-free planar by Cranston & Smith-Roberge (arXiv:2401.01332)
and Cambie–van Batenburg–Zhu (Disjoint list-colorings for planar graphs).
Only an exponential bound in χℓ is known in general: χℓ(G) is at most an
exponential function of χℓ(G) (via Thm 3 and χℓ ≥ C·log δ), which is the
current “modest support” for a linear bound (2110.05230, §1). So the linear
List Packing Conjecture is wide open even up to any constant factor.

The named conjectures.

List Packing Conjecture (Conj. 1, 2110.05230): there is C > 0 with
χ*ℓ(G) ≤ C·χℓ(G) for all G; possibly even (1+ε)χℓ for large χℓ.
Bounded-degree form (Conj. 3, 2303.01246): χ*ℓ(G) ≤ Δ(G) + 1 for all
G (sharp for complete graphs). This is Problem 2.5 in the workshop list.

Settled classes / small cases (2303.01246).

The Δ+1 bound (Conj. 3(i)) is proven for Δ = 2 and Δ = 3 (subcubic).
The correspondence analogue is proven for Δ = 2, 3, 4 (implying χ*c(K₅) = 6).
General bounded-degree improvement: χℓ(G) ≤ χc(G) ≤ 2Δ − 2 for Δ ≥ 4
(Thm 6) — still ~2× the conjecture.
Fractional relaxation is essentially solved: χ•ℓ(G) ≤ χ•c(G) ≤ Δ + 1 for
all G (Thm 7). The fractional List Packing Conjecture holds in strong form.

Take-away. The +1 question (2.1) is known to hold wherever the Δ+1 bound
is proven and χℓ is not far below Δ — most cleanly on subcubic graphs and on
complete graphs — but there is no general theorem forcing the gap ≤ 1, and
the honest general knowledge is only the exponential bound.

3. What’s open

Headline (Problem 2.1). Find a G with χ*ℓ(G) ≥ χℓ(G) + 2, or prove none
exists. Related open problems from the same listing (arXiv:2411.10046, §2):

2.2 — Is χ*ℓ(G) ≤ 2·χℓ(G) always? (Weaker than a linear-constant proof;
even this is open.)
2.5 — Is χ*ℓ(G) ≤ Δ+1 for every G? (Open for Δ ≥ 4.)
2.6 / 2.7 — Is there a planar G with χℓ ≥ 6? Is χℓ ≤ 7 for all planar?
2.8 — Triangle-free planar: is χ*ℓ ≤ 4?
2.9 — Deletion sensitivity: unlike χℓ, the list packing number can drop by
more than one when a single vertex/edge is removed. Is χℓ(G) ≤
χℓ(G∖v) + 2 (and the edge version)? This is why inductive proofs of a +1
bound are hard (see §5).

Decomposed sub-targets where the +1 bound is unproven:

χℓ = 3 graphs (would need χℓ ≥ 5 to break 2.1) — the smallest viable
gap-2 target. The χℓ = 2 route looks closed: 2-choosable cores are
classified (even cycles / θ-graphs, all with χℓ = 3), and any subcubic
graph has χ*ℓ ≤ Δ+1 = 4 by the proven Δ = 3 bound, so no χℓ = 2
counterexample can reach gap 2 in the easiest search region. Verify the
2-choosable characterization (Erdős–Rubin–Taylor) before relying on this.
Δ = 4 and Δ = 5 graphs, where only χ*ℓ ≤ 2Δ−2 is known (gaps 6, 8) and
the Δ+1 target is unproven.
Planar / triangle-free planar (Problems 2.6–2.8): sharp thresholds
unknown; a planar graph with χ*ℓ = 6 would itself be notable.
Correspondence packing χc, where the Catlin construction already gives
χc(Kₙ) = Δ+2 for odd n ≥ 3 — a live example that the correspondence gap
exceeds Δ+1, sharpening the contrast with the list case.

Smallest sizes not yet exhaustively searched: we did not find a published
exhaustive-search frontier (e.g. “all graphs on ≤ N vertices verified to
satisfy gap ≤ 1”). Treat any such number as unestablished until confirmed; a
first contribution could simply be to define and run that frontier (§4).

4. Attack plan

A. Computational counterexample search (falsify 2.1).
Goal: exhibit G, L with a (χℓ+2)-list-assignment admitting no full packing.

Enumerate graphs with geng/nauty up to ~10–12 vertices, filtered to
the promising regimes of §3 (χℓ = 3 with small Δ; Δ = 4).
Reduce the color universe. Verifying χ*ℓ(G) ≤ k means checking all
k-list-assignments — infinite in principle, but only the correspondence
structure (how lists overlap along edges) matters, so WLOG colors come from
a bounded palette (≤ kn) and assignments reduce to permutation/DP-covers.
This is the crucial finiteness lever.
Per-assignment decision. For fixed (G, L), “do k disjoint proper
L-colorings exist?” is an exact-cover / disjoint-list-coloring feasibility
problem — encode as SAT or ILP; small instances solve instantly.
Symmetry reduction. Quotient by graph automorphisms and color
permutations and correspondence-cover isomorphism; without this the
list-assignment count explodes. This is the make-or-break engineering step.
Honest cost note. Computing χℓ itself is Π₂ᵖ-hard (Problem set §2 notes
the complexity of χ*ℓ is essentially unstudied), so brute force does not
scale; the strategy is targeted small regimes, not blanket search. A clean
negative result (“no gap-2 example on ≤ N vertices, Δ ≤ 4”) is itself a
citable, well-documented artifact for the table.

B. Proof directions for restricted classes.

Push the Δ = 4 case of Conj. 3(i) (χ*ℓ ≤ 5) — the first unproven degree,
and the natural next brick after the published Δ = 3 proof.
Attack 2.2 (χ*ℓ ≤ 2χℓ) as a softer target than the +1 bound.
Use the fractional result (Thm 7, χ•ℓ ≤ Δ+1) as a template: find where the
rounding from fractional to integral packing loses more than 1.

C. Counting / sampling sub-thread (the algorithmic cousin).
Instead of existence, study how many packings there are — often a route to
existence via the probabilistic method.

Counting. Kaul & Mudrock, Counting Packings of List-colorings of Graphs
(arXiv:2401.11025, 2024): define a list-packing function P*ℓ(G,q,k) and use a
polynomial method to turn packing-number bounds into exponential lower
bounds (in |V|) on the number of packings for sparse graphs — a “many
packings exist” result that could seed an existence argument.
Sampling. Camrud, Davies, Karduna & Lee, Sampling List Packings
(arXiv:2402.03520, 2024): an FPRAS via rapid mixing of Glauber dynamics
when the number of colors is Ω(Δ²) — an “atypical spin system” (many more
colors than degree). Feasible AI/code contribution: implement the chain,
measure the empirical mixing/packing threshold below Ω(Δ²), and probe whether
the phase where packings become scarce coincides with candidate
counterexample regimes.

5. Known dead ends / hard cases

Naive induction fails (Problem 2.9). χℓ can fall by more than 1 when
you delete a vertex or edge, so the standard “remove a low-degree vertex,
color, extend” argument that proves χℓ ≤ 1+δ does not transfer to χ*ℓ.
Any inductive +1 proof must control this jump — the central obstruction.
Closing the factor-2 gap is “frustratingly difficult” (authors’ own word,
2303.01246 §1): the general bound has been stuck around 2Δ (now 2Δ−2) for
years; even shaving the constant is hard, so a full linear bound is far off.
Only exponential-in-χℓ is known in general — the linear List Packing
Conjecture has essentially no unconditional traction beyond special classes.
Correspondence packing genuinely exceeds Δ+1 (Catlin: χc(Kₙ)=Δ+2, odd
n): a warning that the “+1” intuition is false for the DP variant, so any
proof must use list-specific (not correspondence-general) structure — and any
counterexample search in χc is not automatically a χ*ℓ counterexample.
Complexity is uncharted: deciding χ*ℓ(G) ≤ k is expected to be
Π₂ᵖ-flavored; even the treewidth-bounded case being in P is open (Problem set
§2). Brute-force verification therefore has a hard scaling ceiling.

6. Reading list

Cambie, Cames van Batenburg, Davies, Kang — Packing list-colorings, RSA
64(1) 2024. Foundational; defs, Thms 2–7, Conjecture 1.
[2110.05230] Packing list-colourings
Cambie, Cames van Batenburg, Davies, Kang — List packing number of bounded
degree graphs. Conjecture 3 (Δ+1), subcubic proof, 2Δ−2 bound.
[2303.01246] List packing number of bounded degree graphs
Cambie — Open problems of the 32nd Workshop on Cycles and Colourings,
§2. Problem 2.1 is our headline; 2.2–2.9 are the sub-targets.
[2411.10046] Open problems of the 32nd Workshop on Cycles and Colourings
Cranston & Smith-Roberge — List-Coloring Packing and Correspondence-Coloring
Packing of Planar Graphs. Improved planar bounds (Problems 2.6–2.8).
[2401.01332] List Packing and Correspondence Packing of Planar Graphs
Kaul & Mudrock — Counting Packings of List-colorings of Graphs (2024).
The counting sub-thread. [2401.11025] Counting Packings of List-colorings of Graphs
Camrud, Davies, Karduna, Lee — Sampling List Packings (2024). FPRAS /
Glauber dynamics, the sampling sub-thread. [2402.03520] Sampling List Packings
Cambie & Cames van Batenburg — Fractional list packing for layered graphs
(J. Graph Theory, 2025). Context for the fractional relaxation (Thm 7).

Open verification tasks for the table: (a) confirm the 2-choosable core
classification and its consequence in §3.1; (b) establish whether any published
exhaustive-search frontier exists (§3); (c) re-derive the even-cycle χ*ℓ = 3
computation as a warm-up sanity check for the search code.