# What exactly is a clique cover problem?

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.

-

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.

-
so if I have a clique of size four, of four vertices, how would the graph look like? –  user1675999 Dec 4 '12 at 14:41
The wikipedia page for complete graphs has a bunch of examples (including $K_4$): en.wikipedia.org/wiki/Complete_graph –  William Macrae Dec 4 '12 at 14:45
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? –  user1675999 Dec 4 '12 at 16:47
@user1675999: see this image: cs.mcgill.ca/~ethan/img/cliquecover.png –  Vor Dec 4 '12 at 17:56