Provided that we have to compare it against the graph coloring problem which is NPC. So far, I can only think of connecting edges from a vertex in a provided graph to all the other edges it is not connected to then I separate the new graph g2, then I connect all the vertices that are not connected in the g2. And then I count the number of subsets. However it doesnt seem to work with a graph that requires four colors?

  • $\begingroup$ It sounds like you're already on the right track. Making a vertex adjacent to the vertices it was not adjacent to (and not adjacent to those it was adjacent to) is called taking the complement in graph theory. It seems to be a good choice for a first step. Can you elaborate on why you think your solution does not work for four colors? $\endgroup$ Dec 4, 2012 at 14:29
  • $\begingroup$ say suppose i have clique graph g2 where max clique size is 4, Since they are already all connected/complete graph , I cant do the step that I just mentioned. Also it's a clique cover problem that we have to prove is NPC. I think I don't get what a clique cover problem is? $\endgroup$ Dec 4, 2012 at 14:38
  • $\begingroup$ If your original input is $K_4$, then its complement separates into 4 $K_1$s (single vertices). So you have four cliques that cover the complement and require four colors. If your original input is 4 vertices with no edges, then the complement is a clique, so you can cover the complement with one clique and only need one color. $\endgroup$ Dec 4, 2012 at 14:49

1 Answer 1


In the interests of putting up an explicit answer, your approach is correct. The proof is sketched on the Wikipedia page for Clique Cover.

The reduction itself is fairly straightforward. The reasoning is that if a graph is $k$-colourable, then it can be partitioned into $k$ independent sets (one for each colour class), then we just exploit the normal reduction between Independent Set and Clique by taking the complement graph (we swap edges for non-edges and vice versa), so any independent set becomes a clique. So if $G$ is $k$-colourable, it can be partitioned into $k$ independent sets and hence $\overline{G}$ can be partitioned into (i.e. covered by) $k$ cliques (but not necessarily by $k$-cliques ;) ). Conversely if $\overline{G}$ can be covered by $k$ cliques, $G$ has a partition into $k$ independent sets, and hence is $k$-colourable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.