# Parameter: degeneracy

The following definitions are equivalent:
1. The degeneracy of a graph $G$ is the smallest integer $k$ such that each subgraph of $G$ contains a vertex of degree at most $k$.
2. Let $G$ be a graph and consider the following algorithm:
• Find a vertex $v$ with smallest degree.
• Delete vertex $v$ and its incident edges.
• Repeat as long as the graph is not empty.
The degeneracy of a graph $G$ is the maximum degree of a vertex when it is deleted in the above algorithm.

## Relations

Minimal/maximal is with respect to the contents of ISGCI. Only references for direct bounds are given. Where no reference is given, check equivalent parameters.

[+]Details

[+]Details

## Problems

Problems in italics have no summary page and are only listed when ISGCI contains a result for the current parameter.

3-Colourability Unknown to ISGCI [+]Details
Clique XP [+]Details
Clique cover Unknown to ISGCI [+]Details
Colourability Unknown to ISGCI [+]Details
Domination Unknown to ISGCI [+]Details
Feedback vertex set Unknown to ISGCI [+]Details
Graph isomorphism Unknown to ISGCI [+]Details
Hamiltonian cycle Unknown to ISGCI [+]Details
Hamiltonian path Unknown to ISGCI [+]Details
Independent set Unknown to ISGCI [+]Details
Maximum cut Unknown to ISGCI [+]Details
Monopolarity Unknown to ISGCI [+]Details
Polarity Unknown to ISGCI [+]Details
Weighted clique XP [+]Details
Weighted feedback vertex set Unknown to ISGCI [+]Details
Weighted independent set Unknown to ISGCI [+]Details