Graphs with chromatic numbers strictly less than their colouring numbers

Xuding Zhu

Abstract


The colouring number of a graph G, defined as col(G) = 1+ maxHGδ(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


Chromatic number, colouring number, Szekeres-Wilf inequality, NP-completeness

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.176.704

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications