7
$\begingroup$

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?

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

Yes, and this holds even for structured graphs. Indeed, every planar graph is 5-colorable (in fact even 4-colorable by the Four color theorem), but it is NP-complete to decide if a planar graph can be colored in 3 colors.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.