The core decomposition of a graph 
is the nested family of all k-cores
of 
as 
ranges over the nonnegative integers. Equivalently, it records how vertices survive
the repeated deletion process that defines the 
-cores. The largest 
for which the core decomposition contains a nonempty 
-core is the graph
degeneracy of 
.
The core decomposition can be computed in linear time in the number of edges of the graph (Batagelj and Zaveršnik 2003).
Algorithm for Cores Decomposition of Networks." 25
Oct 2003.