Graphs with chromatic numbers strictly less than their colouring numbers
Xuding Zhu · Ars Mathematica Contemporanea · 2010
The colouring number of a graph G , defined as col( G ) = 1+ max H ⊆ 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.