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
    Yes, this makes perfect sense. Thanks so much.2011-09-30
  • 0
    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?2012-10-31
  • 0
    (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?2012-10-31
  • 0
    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.2012-10-31
  • 0
    @ChrisGodsil: Thanks! (1) " the minimum number of matchings that cover the edges of a graph". Is it still the same when replacing "cover" with "partition"? (2) Yes, an edge clique cover is defined as a set of cliques that cover all edges. "in a triangle-free graph the edge clique cover number is just the number of edges", so it is not true that "the edge clique cover number of a graph is simply equal to the edge chromatic number of the complement of that graph"?2012-10-31
  • 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