Is the 3-coloring problem NP-hard on graphs of maximal degree 3?

Question

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?

Answer 1

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.