# Proving that the clique cover problem is in NPC by reducing from k-coloring

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?

• 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? Dec 4, 2012 at 14:29
• 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? Dec 4, 2012 at 14:38
• 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. Dec 4, 2012 at 14:49

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.