I am really confused about clique problem and clique cover problem. I tried googling it,but I don't see to be able to visualise the clique cover problem.


1 Answer 1


A clique is a simple undirected graph with all of the possible edges. It is also known as a complete graph, but clique is more often used to referring to subgraphs that are complete graphs.

The clique cover problem asks whether a graph's vertices can be partitioned into $k$ or fewer sets such that each set of vertices induces a clique. That is, $V = V_1 \cup V_2 \cdots \cup V_k$ such that if $u, v \in V_i$ then $uv \in E$. For example, $C_4$ (a cycle of 4 vertices) can be partitioned into 2 cliques by choosing two non-adjacent edges. If the vertices were 1, 2, 3, 4 and the edges 12, 23, 34, 14, then we could write $V = \{1,2\} \cup \{3,4\}$, and check that $12$ and $34$ were edges as required.

This is different from the clique problem, which asks whether there is a clique in the graph of size at least $k$ (and does not care about the structure of the rest of the graph. For example, in $C_4$, there is a clique of size 2.

  • $\begingroup$ so if I have a clique of size four, of four vertices, how would the graph look like? $\endgroup$ Commented Dec 4, 2012 at 14:41
  • $\begingroup$ The wikipedia page for complete graphs has a bunch of examples (including $K_4$): en.wikipedia.org/wiki/Complete_graph $\endgroup$ Commented Dec 4, 2012 at 14:45
  • $\begingroup$ what I am confused is according to the question that I was provided, it says clique cover problem exists a partition of V into k disjoint subsets. If that is the case then I can take the clique K4, and break it into V={1,2}U{3,4} and have two subsets, and from another question that I asked, for the four single vertices , will require two colors to color? $\endgroup$ Commented Dec 4, 2012 at 16:47
  • 1
    $\begingroup$ @user1675999: see this image: cs.mcgill.ca/~ethan/img/cliquecover.png $\endgroup$
    – Vor
    Commented Dec 4, 2012 at 17:56

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.