Questions tagged [graph-degeneracy]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
15
votes
0answers
466 views

Linear-time algorithm to test if clique number equals degeneracy bound?

Given a connected simple graph $G=(V,E)$, let $d$ denote its degeneracy and let $\omega$ denote the size of a maximum clique. A well-known bound on the clique number is $\omega\le d+1$, which is ...