Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
Yes, this makes perfect sense. Thanks so much. –  Graphth Sep 30 '11 at 18:16
    
+1! nice answer. –  Tim Oct 30 '12 at 14:57
    
Is it also true that the edge clique cover number of a graph is simply equal to the edge chromatic number of the complement of that graph? –  Tim Oct 31 '12 at 3:11
    
(1) If I am correct, the edge chromatic number of a graph is the minimum number of matchings that can cover the edges of the graph. (2) I am not sure if there is a relation between the minimum number of matchings that can cover the edges of a graph and the edge clique cover number of the complement of the graph. Are they the same? –  Tim Oct 31 '12 at 3:32
    
The edge chromatic number is certainly equal to the minimum number of matchings that cover the edges of a graph (each color class in an edge coloring is a matching). If an edge clique cover is a set of cliques that cover all edges, then in a triangle-free graph the edge clique cover number is just the number of edges. –  Chris Godsil Oct 31 '12 at 4:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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