Weak degeneracy is a relaxation of graph degeneracy that permits one neighbor to be spared a budget decrement during certain vertex
deletions (Bernshteyn and Lee 2023). For a finite simple graph and integer budgets
at its vertices, the ordinary
deletion of
is legal when
;
it removes
and decreases by 1 the budget of every remaining neighbor of
. A deletion that saves an adjacent vertex
instead leaves
unchanged and decreases the budgets of the other neighbors.
This operation is legal when
and
. The graph
is weakly
-degenerate
iff some sequence of legal operations removes all its vertices. Constant initial budgets
define weak
-degeneracy. Every
-degenerate graph is weakly
-degenerate, and every weakly
-degenerate graph is
-choosable and
-correspondence-colorable. Here choosability refers to
list coloring, and the latter property refers to
correspondence coloring.
The availability of an ordinary deletion of is
, while the availability
of a deletion of
saving
is
, using the current budgets. A graph
is
-availably
weakly
-degenerate
when it has a legal removal sequence whose availabilities have geometric
mean at least
(Dvorák and Smith-Roberge 2026). Such a sequence guarantees at least
list
colorings for every assignment with
on an
-vertex graph, and gives the same
bound for correspondence coloring.
Dvorák and Smith-Roberge (2026, Theorem 1.3) proved that every planar graph is -availably
weakly 4-degenerate. In particular, it has at least
valid colorings for any lists of five colors, including
arbitrary correspondence matchings. The deletion sequence depends on the graph
alone, before the lists are given. Their Observation 1.4 also yields a fixed
set
of vertices with
such that every assignment of four colors to each vertex in and five colors to every other vertex admits a list
coloring. This holds as well for arbitrary correspondence matchings. The set
can be chosen independently of the color
lists and matchings.