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

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?

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.