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.
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
4
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$ – user1675999 Dec 4 '12 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$ – William Macrae Dec 4 '12 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$ – user1675999 Dec 4 '12 at 16:47
-
1$\begingroup$ @user1675999: see this image: cs.mcgill.ca/~ethan/img/cliquecover.png $\endgroup$ – Vor Dec 4 '12 at 17:56
