New answers tagged graph-colouring
2
votes
Accepted
Hardness of Maximum Independent Set in 3-Colorable Graphs
As detailed below, the problem of finding an independent set of size $\Omega(n^{1-\delta})$ in 3-colorable graphs is essentially equivalent to $O(n^\delta)$-approximating 3-COLOR. Currently, the best ...
- 9,024
13
votes
Is the 3-coloring problem NP-hard on graphs of maximal degree 3?
The answer is no: the 3-coloring problem can be solved in linear time on graphs of maximal degree 3 or less, by application of Brooks' theorem. I wasted some time figuring this out, so I thought I'd ...
- 7,880
Top 50 recent answers are included