2
$\begingroup$

I have heard that the Vertex Clique Cover Number is equal to the Chromatic Number of the complement of a graph. But, I can't find a reference. Is this true? And, is it true for all graphs or just connected graphs? The vertex clique cover number clear adds over connected components but the chromatic number doesn't... but it's chromatic number of the complement so I'm not sure if that affects things.

Thanks for any help

1 Answers 1

6

The key is to note that the chromatic number of a graph is equal to the minimum number of cocliques (= independent sets = stable sets) that you need to cover the vertices of a graph. (This is reasonably easy to prove and is surprisingly useful. But it's not obvious when you're starting out.)

Given this, it is immediate that the minimum number of cliques you need to cover the vertices is equal to the chromatic number of the complement.

Connectivity plays no role, as you can see.

  • 0
    (1) Yes (an edge coloring of a graph is a vertex coloring of its line graph, so the vertex coloring ideas can be applied). (2) It's not true - think about the complete bipartite graphs $K_{n,n}$.2012-10-31