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!
Best Answer
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.