# Is 3-colouring NP-hard for 5-colourable graphs?

Recently it was shown that it is NP-hard to find a 5-colouring of a 3-colourable graph. More generally, it is NP-hard to distinguish $$k$$-colourable graphs from those that are not $$(2k-1)$$-colourable, for $$k\ge 3$$.

Turning the question around:

Is deciding if a 5-colourable graph is 3-colourable NP-hard?

• It is not the decision problem that is hard; every 3-colorable graph is also 5-colorable. "Distinguish" is not the same as "decide". – Tom van der Zanden Nov 14 '19 at 16:56
• Thanks, corrected. – András Salamon Nov 15 '19 at 6:39