TOPICS
Search

Weak Degeneracy


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 G and integer budgets f(v) at its vertices, the ordinary deletion of v is legal when f(v)>=0; it removes v and decreases by 1 the budget of every remaining neighbor of v. A deletion that saves an adjacent vertex w instead leaves f(w) unchanged and decreases the budgets of the other neighbors. This operation is legal when f(v)>=0 and f(v)>f(w). The graph is weakly f-degenerate iff some sequence of legal operations removes all its vertices. Constant initial budgets f(v)=d define weak d-degeneracy. Every d-degenerate graph is weakly d-degenerate, and every weakly d-degenerate graph is (d+1)-choosable and (d+1)-correspondence-colorable. Here choosability refers to list coloring, and the latter property refers to correspondence coloring.

The availability of an ordinary deletion of v is f(v)+1, while the availability of a deletion of v saving w is f(v)-f(w), using the current budgets. A graph is alpha-availably weakly f-degenerate when it has a legal removal sequence whose availabilities have geometric mean at least alpha (Dvorák and Smith-Roberge 2026). Such a sequence guarantees at least alpha^n list colorings for every assignment with |L(v)|>f(v) on an n-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 2^(1/7)-availably weakly 4-degenerate. In particular, it has at least 2^(n/7) 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 R of vertices with

 |R|>=(ln2)/(7ln5)n>0.06n

such that every assignment of four colors to each vertex in R and five colors to every other vertex admits a list coloring. This holds as well for arbitrary correspondence matchings. The set R can be chosen independently of the color lists and matchings.


See also

Correspondence Coloring, Graph Degeneracy, List Coloring, Planar Graph

Explore with Wolfram|Alpha

References

Bernshteyn, A. and Lee, E. "Weak Degeneracy of Graphs." J. Graph Th. 103, 607-634, 2023. https://doi.org/10.1002/jgt.22938.Dvorák, Z. and Smith-Roberge, E. "Weak Degeneracy with Availability for Planar Graphs." 19 Nov 2026. https://arxiv.org/abs/2611.25850v1.

Cite this as:

Weisstein, Eric W. "Weak Degeneracy." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/WeakDegeneracy.html

Subject classifications