The degeneracy of a graph 
, also known as the 
-core number, graph width, or graph linkage, is defined as
the smallest integer 
such that each subgraph of 
contains a graph
vertex of degree at most 
. Equivalently, the degeneracy of a graph 
is the largest 
for which 
has a k-core.
Graph degeneracy is essentially the same as the coloring number and Szekeres-Wilf number.
k-vertex-connected graphs have degeneracy of at least 
.
(Non-empty) trees and forests have degeneracy 1, (finite) planar graphs have degeneracy at most 5, outerplanar graphs have degeneracy at most 2, and Apollonian networks have degeneracy 3.
The degeneracy of a graph may be computed in linear time by repeatedly removing minimum-degree vertices from a graph.
An arc-weighted graph orientation assigns a positive integer weight 
to each oriented graph
edge. Such a graph orientation is arc-weighted
acyclic if every nonempty subdigraph contains a graph arc 
whose weight
is larger than the weighted outdegree of 
. The arc-weighted degeneracy 
is the least 
for which an arc-weighted acyclic graph
orientation exists with weighted outdegree at most
at every graph
vertex. It satisfies
 |
and the difference can be arbitrarily large. Zhou et al. (2026) prove that 
bounds the DP-paint number and
the Alon-Tarsi number of 
.
-Degenerate Graphs." Canad. J. Math. 22,
1082-1096, 1970.Zhou, H.; Zhu, J.; and Zhu, X. "Arc-Weighted Acyclic
Orientation of Graphs." Electron. J. Combin. 33, P3.83, 2026.