Proving that the clique cover problem is NP completein NPC by reducing from k-coloring

Tweeted twitter.com/#!/StackCompSci/status/276367683522543616
edited tags
Link
Source Link
user1675999
  • 1k
  • 5
  • 15
  • 22

Proving that clique cover problem is NP complete

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?