# Definition of clique cover and clique edge cover

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!

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.
• @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