<p>Suppose we have a graph <span class="math-container">$G$</span> with maximum degree <span class="math-container">$\Delta$</span>. Deciding if <span class="math-container">$G$</span> can be colored with <span class="math-container">$\Delta$</span> colors is easy: Brooks' theorem says that this is always possible, unless <span class="math-container">$G$</span> is a clique or an odd cycle.</p>
<p>I'm interested in the complexity of coloring <span class="math-container">$G$</span> with <span class="math-container">$(\Delta-1)$</span> colors. It is well-known that the case <span class="math-container">$\Delta=4$</span> is NP-complete, as NP-completeness of 3-coloring graphs of maximum degree 4 is already mentioned in Garey&amp;Johnson's book. I would like to know if similar results are known for other small values of <span class="math-container">$\Delta$</span>. For example, I tried searching for the complexity of <span class="math-container">$4$</span>-coloring graphs of maximum degree <span class="math-container">$5$</span>, but failed to find anything relevant.</p>
<p><strong>Question:</strong> For which fixed values of <span class="math-container">$\Delta$</span> is the complexity of <span class="math-container">$(\Delta-1)$</span>-coloring graphs of maximum degree <span class="math-container">$\Delta$</span> known?</p>
<p><strong>Motivation:</strong> I would have initially thought that, since this is NP-hard for <span class="math-container">$\Delta=4$</span>, it would be NP-hard for all larger values of <span class="math-container">$\Delta$</span>. However, it turns out that this is false! According to the main result of [1], &quot;for sufficiently large <span class="math-container">$\Delta$</span>, any graph with maximum degree at most <span class="math-container">$\Delta$</span> and no cliques of size <span class="math-container">$\Delta$</span> has a <span class="math-container">$\Delta−1$</span> colouring&quot;. This implies that for sufficiently large (fixed) <span class="math-container">$\Delta$</span>, the problem is in P by the following simple algorithm: check (in time <span class="math-container">$n^{\Delta}$</span>) if <span class="math-container">$G$</span> contains a clique of size <span class="math-container">$\Delta$</span>; if it does say NO, otherwise say YES.</p>
<p><strong>Question</strong> The above implies that <span class="math-container">$(\Delta-1)$</span>-coloring graphs of max degree <span class="math-container">$\Delta$</span> is in P for sufficiently large <span class="math-container">$\Delta$</span>. What is the smallest concrete value of <span class="math-container">$\Delta$</span> for which this problem is known to be in P?</p>
<p>References:
[1] A Strengthening of Brooks' Theorem, Bruce Reed, JCTB 1999. <a href="https://doi.org/10.1006/jctb.1998.1891" rel="noreferrer">https://doi.org/10.1006/jctb.1998.1891</a></p>

CC BY-SA 4.0
2023-02-08T15:30:36.933Z
This seems relevant: https://doi.org/10.1017/S0963548398003678 See Theorem 1.4.
Heng Guo
CC BY-SA 4.0
2023-02-08T19:54:51.747Z
1. Reed says in that paper that probably one can get that result down to $\Delta \geq 1000$.
2. For $\Delta \geq 13$, if $\chi > \Delta-1$, then there is a $\Delta-3$-clique https://doi.org/10.1137/130929515
3. Other related refs: https://doi.org/10.1080/02331930701779021, https://doi.org/10.1016/j.jctb.2004.09.006, https://doi.org/10.1002/jgt.21847
Joshua Grochow
CC BY-SA 4.0
2023-02-08T20:00:49.130Z
You gave a poly-time decision algorithm based on Reed's result. Do you know how hard it is to *find* a $\Delta-1$ coloring of a graph satisfying the condition of Reed's result?
Joshua Grochow
CC BY-SA 4.0
2023-02-08T21:47:36.157Z
Following my previous comment, the algorithm complementing the hardness is given in: https://doi.org/10.1016/j.jctb.2014.06.004
Heng Guo
<np-hardness><graph-colouring><bounded-degree>
Complexity of $(\Delta-1)$-coloring graphs of maximum degree $\Delta$
Michael Lampis
# Complexity of $(\Delta-1)$-coloring graphs of maximum degree $\Delta$

(Asked by: username_0 on 2023-02-08)

Suppose we have a graph $G$ with maximum degree $\Delta$. Deciding if $G$ can be colored with $\Delta$ colors is easy: Brooks' theorem says that this is always possible, unless $G$ is a clique or an odd cycle.

I'm interested in the complexity of coloring $G$ with $(\Delta-1)$ colors. It is well-known that the case $\Delta=4$ is NP-complete, as NP-completeness of 3-coloring graphs of maximum degree 4 is already mentioned in Garey&Johnson's book. I would like to know if similar results are known for other small values of $\Delta$. For example, I tried searching for the complexity of $4$-coloring graphs of maximum degree $5$, but failed to find anything relevant.

**Question:** For which fixed values of $\Delta$ is the complexity of $(\Delta-1)$-coloring graphs of maximum degree $\Delta$ known?

**Motivation:** I would have initially thought that, since this is NP-hard for $\Delta=4$, it would be NP-hard for all larger values of $\Delta$. However, it turns out that this is false! According to the main result of [1], "for sufficiently large $\Delta$, any graph with maximum degree at most $\Delta$ and no cliques of size $\Delta$ has a $\Delta−1$ colouring". This implies that for sufficiently large (fixed) $\Delta$, the problem is in P by the following simple algorithm: check (in time $n^{\Delta}$) if $G$ contains a clique of size $\Delta$; if it does say NO, otherwise say YES.

**Question** The above implies that $(\Delta-1)$-coloring graphs of max degree $\Delta$ is in P for sufficiently large $\Delta$. What is the smallest concrete value of $\Delta$ for which this problem is known to be in P?

References:
[1] A Strengthening of Brooks' Theorem, Bruce Reed, JCTB 1999. <https://doi.org/10.1006/jctb.1998.1891>

**Tags:** np-hardness, graph-colouring, bounded-degree

> **Comments:**
> **username_1**: This seems relevant: https://doi.org/10.1017/S0963548398003678 See Theorem 1.4.  
> **username_2**: 1. Reed says in that paper that probably one can get that result down to $\Delta \geq 1000$. 2. For $\Delta \geq 13$, if $\chi > \Delta-1$, then there is a $\Delta-3$-clique https://doi.org/10.1137/130929515 3. Other related refs: https://doi.org/10.1080/02331930701779021, https://doi.org/10.1016/j.jctb.2004.09.006, https://doi.org/10.1002/jgt.21847  
> **username_2**: You gave a poly-time decision algorithm based on Reed's result. Do you know how hard it is to *find* a $\Delta-1$ coloring of a graph satisfying the condition of Reed's result?  
> **username_1**: Following my previous comment, the algorithm complementing the hardness is given in: https://doi.org/10.1016/j.jctb.2014.06.004  

---

## 0 answers

