Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

From Wikipedia

The clique cover problem (also sometimes called partition into cliques) is the problem of determining whether the vertices of a graph can be partitioned into k cliques.

It seems to me that a clique cover is defined as a set of cliques that partition the vertices of the graph.

From Wikipedia:

An alternative definition of the intersection number of a graph G is that it is the smallest number of cliques in G (complete subgraphs of G) that together cover all of the edges of G. A set of cliques with this property is known as a clique edge cover or edge clique cover,

It seems to me that a clique edge cover is defined as a set of cliques that cover the vertices of the graph.

The two don't seem consistent to me. I searched in Douglas West's Introduction to Graph theory, Both clique cover and clique edge cover are defined in terms of cover instead of partition. So I wonder if the definition for clique cover in Wikipedia is wrong?

Thanks!

share|improve this question

1 Answer 1

up vote 2 down vote accepted

A vertex clique cover is a set of cliques that cover all the vertices of a graph. If they overlapped, say two cliques shared the vertex $v$, we could simply delete $v$ from one of the two cliques and we'd end up with a vertex clique cover that is the same size or smaller (smaller if the clique was just $v$). So, in this case, we go ahead and define the cliques to be disjoint. The vertex clique cover number is the smallest number of such cliques needed to cover all the vertices. This number would be the same whether we specified disjoint cliques or not, because if a minimum vertex clique cover contained cliques that overlapped, we could delete out vertices from one or the other until they no longer overlapped. So, it is equivalent to partitioning the vertices into cliques.

An edge clique cover is a set of cliques that cover all the edges. We can not guarantee that these will be disjoint, so talking about a partition makes no sense in this case. Take a star, for example, $K_{1, 3}$. To cover all 3 edges, we will need each edge to be a clique and all 3 cliques will contain the central vertex of the star. Again, we can define the edge clique cover number as the smallest number of such cliques needed to cover all edges.

Thus, both could be considered in terms of covers, but only the vertex clique cover could be considered in terms of partitions.

It is clear from these definitions that vertex clique cover number is less than or equal to edge clique cover number. Also, the vertex clique cover number of a graph is simply equal to the chromatic number of the complement of that graph. See here for the basic idea of a proof.

share|improve this answer
    
Thanks! (1) "vertex clique cover number is less than or equal to edge clique cover number". Is it because from each edge clique cover, we can construct a vertex clique cover with the same size? (2) " the vertex clique cover number of a graph is simply equal to the chromatic number of the complement of that graph." Is it also true that the edge clique cover number of a graph is simply equal to the edge chromatic number of the complement of that graph? –  Tim Oct 31 '12 at 2:48
    
@tim (1) It's because any edge clique cover must automatically cover all the vertices (okay, assuming the graph has no isolated vertices, I should have mentioned that) (2) No, good question, but I just looked up edge chromatic number and it's always either $\Delta$ or $\Delta + 1$ for every graph, where $\Delta$ is the largest degree. But, edge clique cover number does not require this at all. For example, any complete graph, $K_n$, has edge clique cover number 1, whereas it has edge chromatic number $n$. –  Graphth Nov 1 '12 at 12:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.