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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.