<p>Supposedly the reference "NP-complete problems on a 3-connected cubic planar graph and their applications" by Uehara (a paper I haven't actually seen) proves that independent set is NP-complete even for triangle-free planar graphs. But by <a href="http://en.wikipedia.org/wiki/Gr%C3%B6tzsch%27s_theorem">Grötzsch's theorem</a> they are always 3-colorable, and testing for smaller numbers of colors than 3 is easy in any graph, so they can be optimally colored in P.</p>

<p><a href="http://en.wikipedia.org/wiki/Circle_graph">Circle graphs</a> have the opposite property: for them, coloring is NP complete but the independent set problem is easy.</p>

CC BY-SA 3.0
2012-04-04T00:12:25.400Z
Are you sure about circle graphs? The [wiki](http://en.wikipedia.org/wiki/Circle_graph#Chromatic_number) page says "the chromatic number of a circle graph may be arbitrarily large, and determining the chromatic number of a circle graph is NP-complete."
Ankur
CC BY-SA 3.0
2012-04-04T01:01:52.673Z
Oops, got it backwards. Will fix.
David Eppstein
CC BY-SA 3.0
2012-04-04T15:31:26.850Z
Thanks. It would be great to get other examples. 
The paper by Uehara seems somewhat isolated; there are not too many other papers citing it. I am not even sure if it has been peer reviewed and published.
Ankur
CC BY-SA 3.0
2012-04-03T21:04:53.497Z
2012-04-04T01:02:25.497Z
2012-04-04T01:02:25.497Z
David Eppstein
<p>This is not a new answer but rather a clarification the first and easy-to-obtain reference for hardness of INDEPENDENT SET in triangle-free cubic planar graphs:
The note by Owen Murphy, <em>Computing independent sets in graphs with large girth</em>, <a href="http://www.sciencedirect.com/science/article/pii/0166218X92900418">Discrete Applied Mathematics 35 (1992) 167-170</a> 
proves that </p>

<blockquote>
  <p>INDEPENDENT SET is NP-complete for cubic planar $n$-vertex graphs of girth at least $cn^k$ for any given constants $c&gt;0$ and $k, 0\le k &lt; 1$. </p>
</blockquote>

<p>(In particular, INDEPENDEN SET is NP-complete for cubic planar graphs without cycles of length less than $c$ for any constant $c&gt;0$)</p>

<p>The reduction indicated by @BartJansen is a special case in Murphy's proof of his theorem. </p>

<p>For the opposite property, <a href="http://en.wikipedia.org/wiki/Line_graph">line graphs</a> seem to be more natural than circle graphs as addressed by @DavidEppstein. 
For line graphs, COLOURING is NP-complete but  INDEPENDENT SET is easy.</p>

CC BY-SA 3.0
2013-03-15T11:57:05.047Z
Another interesting example for the opposite property is the class of well-covered graphs (see [here](http://cstheory.stackexchange.com/questions/7645/maximal-maximum-independent-sets/) and [here](http://cstheory.stackexchange.com/questions/7717/complexity-of-finding-the-smallest-well-covered-completion)). For them, Coloring is hard but Independent Set is trivially easy.
vb le
CC BY-SA 3.0
2013-03-13T18:42:05.433Z
2013-03-14T10:56:52.240Z
2013-03-14T10:56:52.240Z
user13136
<p>A perhaps more general statement (with an easy proof) is that the following problem is already NP-complete:</p>

<p>Input: A graph G, a 3-coloring of G, an integer k.</p>

<p>Question: Does G have an independent set of size k?</p>

<p>This can be proven by a reduction from Independent Set. Observe that if we take a graph G, pick some edge, and subdivide it twice (i.e. replace edge {u,v} by a path u,x,y,v where x and y have degree two) then the independence number of G increases by exactly one. (You can add exactly one of x or y to any set which was independent in G, and the reverse is not difficult either.) So the question if graph G with m edges has an independent set of size k, is equivalent to the question whether G', which is the result of subdividing all edges in G twice, has an independent set of size k + m. But note that it is easy to get a 3-coloring of G', by partitioning G' into three independent sets as follows: one contains the vertices which were also in G, and the other two classes each contain exactly one of the two "subdivider" vertices for each edge. Hence this procedure constructs a graph G' with a 3-coloring of it, such that computing its independence number gives you the independence number of the original graph G.</p>

CC BY-SA 3.0
2012-04-04T21:22:42.663Z
This reduction also immediately proves the hardness of independent set in triangle-free planar graphs, from my answer, without reference to difficult-to-obtain papers.
David Eppstein
CC BY-SA 3.0
2012-04-04T16:45:55.460Z
2012-04-04T16:45:55.460Z
Bart Jansen
<p>Is there an example of a class of graphs for which the vertex coloring problem is in P but the independent set is problem is NP complete?</p>

CC BY-SA 3.0
2012-04-03T23:46:47.710Z
there is a sense in which computation of either one is apparently tightly coupled, see the [lovasz sandwich thm](http://en.wikipedia.org/wiki/Lov%C3%A1sz_number) etc
vzn
<cc.complexity-theory><graph-theory><complexity-classes>
graphs where vertex coloring is in P but independent set is NP complete
Ankur
# graphs where vertex coloring is in P but independent set is NP complete

(Asked by: username_0 on 2012-04-03)

Is there an example of a class of graphs for which the vertex coloring problem is in P but the independent set is problem is NP complete?

**Tags:** cc.complexity-theory, graph-theory, complexity-classes
> **Comments:**
> **username_1**: there is a sense in which computation of either one is apparently tightly coupled, see the [lovasz sandwich thm](http://en.wikipedia.org/wiki/Lov%C3%A1sz_number) etc  

---

## 3 answers

### Answer by username_5 on 2012-04-04. Score: 21 | Accepted answer

A perhaps more general statement (with an easy proof) is that the following problem is already NP-complete:

Input: A graph G, a 3-coloring of G, an integer k.

Question: Does G have an independent set of size k?

This can be proven by a reduction from Independent Set. Observe that if we take a graph G, pick some edge, and subdivide it twice (i.e. replace edge {u,v} by a path u,x,y,v where x and y have degree two) then the independence number of G increases by exactly one. (You can add exactly one of x or y to any set which was independent in G, and the reverse is not difficult either.) So the question if graph G with m edges has an independent set of size k, is equivalent to the question whether G', which is the result of subdividing all edges in G twice, has an independent set of size k + m. But note that it is easy to get a 3-coloring of G', by partitioning G' into three independent sets as follows: one contains the vertices which were also in G, and the other two classes each contain exactly one of the two "subdivider" vertices for each edge. Hence this procedure constructs a graph G' with a 3-coloring of it, such that computing its independence number gives you the independence number of the original graph G.

> **Comments:**
> **username_2**: This reduction also immediately proves the hardness of independent set in triangle-free planar graphs, from my answer, without reference to difficult-to-obtain papers.  

---

### Answer by username_2 on 2012-04-03. Score: 22

Supposedly the reference "NP-complete problems on a 3-connected cubic planar graph and their applications" by Uehara (a paper I haven't actually seen) proves that independent set is NP-complete even for triangle-free planar graphs. But by [Grötzsch's theorem](http://en.wikipedia.org/wiki/Gr%C3%B6tzsch%27s_theorem) they are always 3-colorable, and testing for smaller numbers of colors than 3 is easy in any graph, so they can be optimally colored in P.

[Circle graphs](http://en.wikipedia.org/wiki/Circle_graph) have the opposite property: for them, coloring is NP complete but the independent set problem is easy.

> **Comments:**
> **username_0**: Are you sure about circle graphs? The [wiki](http://en.wikipedia.org/wiki/Circle_graph#Chromatic_number) page says "the chromatic number of a circle graph may be arbitrarily large, and determining the chromatic number of a circle graph is NP-complete."  
> **username_2**: Oops, got it backwards. Will fix.  
> **username_0**: Thanks. It would be great to get other examples.  The paper by Uehara seems somewhat isolated; there are not too many other papers citing it. I am not even sure if it has been peer reviewed and published.  

---

### Answer by username_3 on 2013-03-13. Score: 11

This is not a new answer but rather a clarification the first and easy-to-obtain reference for hardness of INDEPENDENT SET in triangle-free cubic planar graphs:
The note by Owen Murphy, *Computing independent sets in graphs with large girth*, [Discrete Applied Mathematics 35 (1992) 167-170](http://www.sciencedirect.com/science/article/pii/0166218X92900418)
proves that

> INDEPENDENT SET is NP-complete for cubic planar $n$-vertex graphs of girth at least $cn^k$ for any given constants $c>0$ and $k, 0\le k < 1$.

(In particular, INDEPENDEN SET is NP-complete for cubic planar graphs without cycles of length less than $c$ for any constant $c>0$)

The reduction indicated by @BartJansen is a special case in Murphy's proof of his theorem.

For the opposite property, [line graphs](http://en.wikipedia.org/wiki/Line_graph) seem to be more natural than circle graphs as addressed by @DavidEppstein.
For line graphs, COLOURING is NP-complete but INDEPENDENT SET is easy.

> **Comments:**
> **username_4**: Another interesting example for the opposite property is the class of well-covered graphs (see [here](http://cstheory.stackexchange.com/questions/7645/maximal-maximum-independent-sets/) and [here](http://cstheory.stackexchange.com/questions/7717/complexity-of-finding-the-smallest-well-covered-completion)). For them, Coloring is hard but Independent Set is trivially easy.  

---

