12
$\begingroup$

Consider the 3-coloring problem: given an undirected graph $G = (V, E)$, decide if there is a 3-coloring of $G$, i.e., a function $f$ from $G$ to $\{1, 2, 3\}$ such that there is no edge $\{u, v\}$ in $E$ with $f(u) = f(v)$. The 3-coloring problem is NP-hard when the input graphs are arbitrary.

It is known that the 3-coloring problem is NP-hard even if the input graph is required to be planar and have maximal degree 4: see Garey, Johnson, Stockmeyer, "Some simplified NP-complete graph problems", 1976.

Does the same hold with a degree bound of 3? Given a graph of maximal degree 3, is it still NP-hard to decide whether it admits a 3-coloring?

$\endgroup$

1 Answer 1

17
$\begingroup$

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 document it in a question here.

Brooks' theorem says that every graph with maximal degree $\Delta$ is $\Delta$-colorable unless one of its connected components is a clique (i.e., the complete graph $K_{\Delta+1}$ with $\Delta+1$ vertices) or, for $\Delta = 2$, if one of its connected components is a cycle of odd length. In particular, for $\Delta = 3$, every graph with maximal degree at most 3 is 3-colorable unless one of its connected components is isomorphic to $K_4$. This condition can be tested in polynomial time on the input graph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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