# graphs where vertex coloring is in P but independent set is NP complete

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?

• there is a sense in which computation of either one is apparently tightly coupled, see the lovasz sandwich thm etc
– vzn
Apr 3 '12 at 23:46

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.

• 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. Apr 4 '12 at 21: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 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 have the opposite property: for them, coloring is NP complete but the independent set problem is easy.

• Are you sure about circle graphs? The wiki 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." Apr 4 '12 at 0:12
• Oops, got it backwards. Will fix. Apr 4 '12 at 1:01
• 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. Apr 4 '12 at 15:31

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 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 seem to be more natural than circle graphs as addressed by @DavidEppstein. For line graphs, COLOURING is NP-complete but INDEPENDENT SET is easy.

• Another interesting example for the opposite property is the class of well-covered graphs (see here and here). For them, Coloring is hard but Independent Set is trivially easy. Mar 15 '13 at 11:57