Degeneracy d(G): smallest k such that every subgraph has a vertex of degree ≤ k. Equivalent: maximum k such that G has a non-empty k-core. d(planar) ≤ 5. χ(G) ≤ d(G)+1. Computable in O(n+m) time. d = col(G)-1 (coloring number).
How to Use
Select graph:
- d: Degeneracy
- k-cores: Nested cores
- Order: Removal sequence
k-Core Decomposition
k-core: maximal subgraph with minimum degree ≥ k. The cores are nested: 0-core ⊇ 1-core ⊇ ... ⊇ d-core. The d-core is the 'densest' part. Social network analysis uses cores to find cohesive groups.
Linear-Time Algorithm
Iteratively remove minimum-degree vertex: the maximum degree removed is d(G). This gives a d(G)+1 coloring (greedy on reverse order). O(n+m) using bucket queue. Practical and widely implemented.
Step-by-Step Instructions
- 1Select graph.
- 2Compute degeneracy.
- 3Find k-cores.
- 4Get removal order.
- 5Apply coloring bound.