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?
Tell me more
×
Computer Science Stack Exchange is a question and answer site for
students, researchers and practitioners of computer science. It's 100% free, no registration required.
|
|
|||||||
|
|
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. |
|||
|
|
