Question: What is the relationship between minimum vertex cover of a graph G and minimum clique cover of conflict graph of G?
Thanks!
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.
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.
