<p>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 <a href="https://en.wikipedia.org/wiki/Brooks%27_theorem" rel="nofollow noreferrer">Brooks' theorem</a>. I wasted some time figuring this out, so I thought I'd document it in a question here.</p>
<p>Brooks' theorem says that every graph with maximal degree <span class="math-container">$\Delta$</span> is <span class="math-container">$\Delta$</span>-colorable unless one of its connected components is a clique (i.e., the complete graph <span class="math-container">$K_{\Delta+1}$</span> with <span class="math-container">$\Delta+1$</span> vertices) or, for <span class="math-container">$\Delta = 2$</span>, if one of its connected components is a cycle of odd length. In particular, for <span class="math-container">$\Delta = 3$</span>, every graph with maximal degree at most 3 is 3-colorable unless one of its connected components is isomorphic to <span class="math-container">$K_4$</span>. This condition can be tested in linear time on the input graph.</p>

CC BY-SA 4.0
2022-11-21T16:52:04.813Z
2024-06-11T19:59:33.033Z
2024-06-11T19:59:33.033Z
Antoine Amarilli 'a3nm'
<p>Consider the 3-coloring problem: given an undirected graph <span class="math-container">$G = (V, E)$</span>, decide if there is a 3-coloring of <span class="math-container">$G$</span>, i.e., a function <span class="math-container">$f$</span> from <span class="math-container">$G$</span> to <span class="math-container">$\{1, 2, 3\}$</span> such that there is no edge <span class="math-container">$\{u, v\}$</span> in <span class="math-container">$E$</span> with <span class="math-container">$f(u) = f(v)$</span>. The 3-coloring problem is NP-hard when the input graphs are arbitrary.</p>
<p>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 <a href="https://www.sciencedirect.com/science/article/pii/0304397576900591" rel="noreferrer">Garey, Johnson, Stockmeyer, &quot;Some simplified NP-complete graph problems&quot;, 1976</a>.</p>
<p>Does the same hold with a degree bound of 3? <strong>Given a graph of maximal degree 3, is it still NP-hard to decide whether it admits a 3-coloring?</strong></p>

<cc.complexity-theory><ds.algorithms><graph-algorithms><graph-colouring><bounded-degree>
Is the 3-coloring problem NP-hard on graphs of maximal degree 3?
Antoine Amarilli 'a3nm'
# Is the 3-coloring problem NP-hard on graphs of maximal degree 3?

(Asked by: username_0 on 2022-11-21)

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](https://www.sciencedirect.com/science/article/pii/0304397576900591).

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?**

**Tags:** cc.complexity-theory, ds.algorithms, graph-algorithms, graph-colouring, bounded-degree

---

## 1 answers

### Answer by username_0 on 2022-11-21. Score: 22 | Accepted answer

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](https://en.wikipedia.org/wiki/Brooks%27_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 linear time on the input graph.


---

