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?

  • 1k
  • 5
  • 15
  • 22