Graphs with chromatic numbers strictly less than their colouring numbers - Zhu, Xuding (Ars mathematica contemporanea, 2011)
The colouring number of a graph ?$G$?, defined as col?$(G) = 1 + \max_{H\subseteq G} δ (H)$?, is an upper bound for its chromatic number. In this note, we prove that it is NP-complete to determine whether an arbitrary graph ?$G$? has chromatic number strictly less than its colouring number.
Keywords: barvanje; chromatic number; colouring number; graph theory; kromatično število; NP-completeness; NP-polnost; Szekeres-Wilf inequality; teorija grafov