<p>Knowing the exact value of the chromatic number $\chi$ cannot help by more than a factor of $n$.  Since there are only $n$ possible values of $\chi$, you can 'guess' its value, i.e., run processes $P_1,\dots,P_n$, where $P_i$ runs an algorithm assuming $\chi=i$.  This whole scheme can find an optimum colouring in time at most $n$ times the time that it takes $P_\chi$ to find an optimum colouring.</p>

<p>On the other hand, if you're talking about parameterizing the running time by $\chi$, then it's a much more interesting question.  It's in FPT if you parameterize by $n-\chi$ <a href="http://www.springerlink.com/content/6kl7ftvl7657jrj3/" rel="nofollow">S. Khot and V. Raman, ‘Parameterized Complexity of Finding Subgraphs with
Hereditary properties’</a>.  If you parameterize by $\chi$ I would assume it's W[1]-hard.</p>

CC BY-SA 2.5
2011-01-19T19:29:14.943Z
Similar argument: if there exists a polynomial-time (deterministic) algorithm, then it can detect in polynomial time if it has been fooled, that is if the input graph really admits a $k$-coloration. Then we can solve the decision problem in polynomial time, and in particular decides if a graph admits a $3$-coloration (which is NP-complete).
Mathieu Chapelle
CC BY-SA 2.5
2011-01-19T19:33:25.267Z
And by similar arguments, I think that when parameterized by $\chi$, the problem is paraNP-complete (above the parameterized W hierarchy), as it is already NP-complete for $\chi = 3$.
Mathieu Chapelle
CC BY-SA 2.5
2011-01-19T18:26:07.970Z
2011-01-19T18:26:07.970Z
James King
<p>Actually, Guruswami <em>et al.</em> proved in [1] that it is NP-complete to find a 4-coloring of a 3-colorable graph, even on bounded-degree graphs.  </p>

<p>This result, initially proven in [2] (but without the bounded-degree condition), implies that it is NP-hard to color a $k$-colorable graph with at most $k + 2\lfloor k/3 \rfloor - 1$ colors.</p>

<p>[1] V. Guruswami, S. Khanna. <em>On the hardness of 4-coloring a 3-colorable graph</em>. In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity (2000). <a href="http://dx.doi.org/10.1109/CCC.2000.856749">http://dx.doi.org/10.1109/CCC.2000.856749</a><br>
[2] S. Khanna, N. Linial, S. Safra. <em>On the hardness of approximating the chromatic number</em>. Combinatorica 20(3) (2000). <a href="http://dx.doi.org/10.1007/s004930070013">http://dx.doi.org/10.1007/s004930070013</a></p>

CC BY-SA 3.0
2013-05-18T21:00:16.493Z
Could you point me to (or explain briefly) the $k + 2 \left \lfloor k/3 \right \rfloor -1$ implication?
Jeremy Kun
CC BY-SA 3.0
2013-05-18T23:11:54.267Z
I found it in the second paper, section 4.4 corollary 1, proof omitted. Is it that obvious and I'm just not seeing it?
Jeremy Kun
CC BY-SA 2.5
2011-01-19T18:05:38.590Z
2011-01-19T19:25:49.460Z
2011-01-19T19:25:49.460Z
Mathieu Chapelle
<p>The result of <a href="http://dx.doi.org/10.1016/0304-3975%2891%2990081-C" rel="nofollow">Khuller and Vazirani</a> shows that finding the lexicographically first four-coloring for planar graphs is $NP$-hard.</p>

CC BY-SA 2.5
2011-01-19T18:00:11.597Z
2011-01-19T18:00:11.597Z
Mohammad Al-Turkistany
<p>We know that graph coloring is NP-complete even in some special graph classes. On the other hand if someone tells you the exact value of the chromatic number of the input graph, is this problem remains NP-complete. In other words I am wondering if there are any result for the search version of the coloring problem (possibly on different graph classes).</p>

<cc.complexity-theory><reference-request><graph-colouring>
Hardness of finding a graph coloring given the optimal number of colors
Arman
# Hardness of finding a graph coloring given the optimal number of colors

(Asked by: username_0 on 2011-01-19)

We know that graph coloring is NP-complete even in some special graph classes. On the other hand if someone tells you the exact value of the chromatic number of the input graph, is this problem remains NP-complete. In other words I am wondering if there are any result for the search version of the coloring problem (possibly on different graph classes).

**Tags:** cc.complexity-theory, reference-request, graph-colouring

---

## 3 answers

### Answer by username_1 on 2011-01-19. Score: 9

Knowing the exact value of the chromatic number $\chi$ cannot help by more than a factor of $n$. Since there are only $n$ possible values of $\chi$, you can 'guess' its value, i.e., run processes $P\_1,\dots,P\_n$, where $P\_i$ runs an algorithm assuming $\chi=i$. This whole scheme can find an optimum colouring in time at most $n$ times the time that it takes $P\_\chi$ to find an optimum colouring.

On the other hand, if you're talking about parameterizing the running time by $\chi$, then it's a much more interesting question. It's in FPT if you parameterize by $n-\chi$ [S. Khot and V. Raman, ‘Parameterized Complexity of Finding Subgraphs with
Hereditary properties’](http://www.springerlink.com/content/6kl7ftvl7657jrj3/). If you parameterize by $\chi$ I would assume it's W[1]-hard.

> **Comments:**
> **username_2**: Similar argument: if there exists a polynomial-time (deterministic) algorithm, then it can detect in polynomial time if it has been fooled, that is if the input graph really admits a $k$-coloration. Then we can solve the decision problem in polynomial time, and in particular decides if a graph admits a $3$-coloration (which is NP-complete).  
> **username_2**: And by similar arguments, I think that when parameterized by $\chi$, the problem is paraNP-complete (above the parameterized W hierarchy), as it is already NP-complete for $\chi = 3$.  

---

### Answer by username_2 on 2011-01-19. Score: 8

Actually, Guruswami *et al.* proved in [1] that it is NP-complete to find a 4-coloring of a 3-colorable graph, even on bounded-degree graphs.

This result, initially proven in [2] (but without the bounded-degree condition), implies that it is NP-hard to color a $k$-colorable graph with at most $k + 2\lfloor k/3 \rfloor - 1$ colors.

[1] V. Guruswami, S. Khanna. *On the hardness of 4-coloring a 3-colorable graph*. In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity (2000). <http://dx.doi.org/10.1109/CCC.2000.856749>  
[2] S. Khanna, N. Linial, S. Safra. *On the hardness of approximating the chromatic number*. Combinatorica 20(3) (2000). <http://dx.doi.org/10.1007/s004930070013>

> **Comments:**
> **username_3**: Could you point me to (or explain briefly) the $k + 2 \left \lfloor k/3 \right \rfloor -1$ implication?  
> **username_3**: I found it in the second paper, section 4.4 corollary 1, proof omitted. Is it that obvious and I'm just not seeing it?  

---

### Answer by username_4 on 2011-01-19. Score: 1

The result of [Khuller and Vazirani](http://dx.doi.org/10.1016/0304-3975%2891%2990081-C) shows that finding the lexicographically first four-coloring for planar graphs is $NP$-hard.


---

