Let G be a connected graph without loops.
The (vertex) independence number is the maximum size of a set of vertices such that no two vertices in the set are connected by an edge.
The (vertex) clique cover number is the minimum number of cliques in G which cover all the vertices of G (not necessarily all the edges of G).
My question is – under what conditions are those two numbers equal?
Best Answer
As BS pointed out, by the perfect graph theorem, being perfect (nicely characterized by the strong perfect graph theorem) is a sufficient condition for what you want. However it is certainly not necessary. Take for instance the disjoint union of the complete graph on 3 vertices and an odd cycle with at least 5 elements. The graph is not perfect but has chromatic number 3 and clique number 3. Its complement is connected, not perfect (again by the perfect graph theorem), and has vertex independence number equal to the least size of a cover by cliques.
This (pathological) example shows that it might be difficult to come up with reasonable conditions that are both necessary and sufficient. This example also shows why the focus has been on perfect graphs, i.e., (by the perfect graph theorem) graphs that have your property hereditarily (for all induced subgraphs).