The list packing number of a finite simple
graph
is the least positive integer
such that every assignment of a
-element color list
to each graph vertex admits
proper list colorings
with
whenever
(Cambie et al. 2024). Thus the colorings collectively
use each available color exactly once at each graph vertex.
The correspondence packing number
imposes the analogous requirement on every
-fold correspondence
coloring cover. It requires a partition of the cover into
independent vertex sets,
each meeting every color list exactly once. In particular,
, where
is the choice number.
Cambie et al. (2026) proved
where
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
-minor-free graph. For graphs
with maximum average degree less than
, 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 . 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 of forbidden partners of a single color in a correspondence
coloring cover of a finite bipartite
graph. For each integer
, every such cover with
colors at each graph vertex admits a partition into
independent transversals, hence a full correspondence packing. Thus
suffices, without bounding the degree of the
underlying bipartite graph. Another sufficient
condition for lists of size
is that every color have at most
forbidden partners. Zhang (2026) attributes the
displayed explicit choice of
, following his asymptotic proof,
to a suggestion by GPT-6.1 Sol.