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?
graphs where vertex coloring is in P but independent set is NP complete
cc.complexity theory;graph theory;complexity classes
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.