patternMinor
Is 3-colouring NP-hard for 5-colourable graphs?
Viewed 0 times
graphshardcolourableforcolouring
Problem
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?
More generally, it is NP-hard to distinguish $k$-colourable graphs from those that are not $(2k-1)$-colourable, for $k\ge 3$.
- J Bulín, A Krokhin, J Opršal. Algebraic Approach to Promise Constraint Satisfaction, STOC 2019. doi:10.1145/3313276.3316300 (preprint)
Turning the question around:
Is deciding if a 5-colourable graph is 3-colourable NP-hard?
Solution
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.
Context
StackExchange Computer Science Q#117102, answer score: 9
Revisions (0)
No revisions yet.