Graph coloring upper bound

601 views Asked by At

Wikipedia states for graph coloring the following upperbound:

X(G)*(X(G) - 1) = 2 * #edges

But I don't understand why this is. The give. Information is unclear to me.

Someone who can help me?

1

There are 1 answers

0
Lrrr On BEST ANSWER

in here it is so clear,by the way the sentence is

In an optimal coloring there must be at least one of the graph’s m edges between every pair of color classes

I'll break it down and make every part more clear.

  • In an optimal coloring : this means that you found a coloring in graph that you cant reduce any more color from it, and if you reduce one color there will be two similar color neighbors.

  • must be at least one of the graph’s m edges between every pair of color classes : Consider the optimal coloring from the first part, it there was two colors for example A and B that there is no edge between A colored nodes and B colored nodes(unlike this statement) then we could change colors of all the A colored nodes to color B, but it is a contradiction from the first statement.

  • From first two statement we have the formula :

    • we have X(G)(X(G) - 1)/2 pairs of color in this coloring.
    • there is at least one edge between all this pairs.
    • so we have X(G)(X(G) - 1) /2 less than equals m so we have :

enter image description here