Question: What is the relationship between minimum vertex cover of a graph G and minimum clique cover of conflict graph of G?


I believe the minimum vertex cover of G is equivalent to minimum clique cover of the conflict graph of G, or their sizes are equal, but today I find a counterexample.

Example: in the figure below, a minimum vertex cover is {1, 2}, but the minimum clique cover contains one partition, that is vertext set {$e_1, e_2, e_3$}. The size of minimum vertex cover is 2, while the size of minimum clique cover is 1. enter image description here

A graph is an ordered pair G = (V, E) comprising a set V of vertices, nodes or points together with a set E of edges, arcs or lines, which are 2-element subsets of V (i.e., an edge is associated with two vertices, and the association takes the form of the unordered pair of the vertices).

A vertex cover of a graph G is a set S of vertices of G such that every edge of G has at least one of member of S as an endpoint.

A minimum vertex cover is a vertex cover having the smallest possible number of vertices for a given graph.

A conflict graph is the graph G = (V, E) where every edge in E is represented by a vertex. Two vertices are adjacent if and only if the edges in E these vertices correspond to intersect each other.

A clique cover or partition into cliques of a graph is a partition of the vertices of the graph into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that uses as few cliques as possible.


The minimum clique cover of the conflict graph is at most the minimum vertex cover of the original graph. In other words, if the original graph has a vertex cover of size $k$, then the conflict graph has a clique cover of size $k$. This is essentially because all edges adjacent to a vertex in the original graph constitute a clique in the conflict graph (though as the example of the triangle shows, there are also other cliques in the conflict graph). Details left to you.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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