Wikipedia states for graph coloring the following upperbound:
But I don't understand why this is. The give. Information is unclear to me.
Someone who can help me?
Wikipedia states for graph coloring the following upperbound:
But I don't understand why this is. The give. Information is unclear to me.
Someone who can help me?
in here it is so clear,by the way the sentence is
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 exampleA
andB
that there is no edge betweenA
colored nodes andB
colored nodes(unlike this statement) then we could change colors of all theA
colored nodes to colorB
, but it is a contradiction from the first statement.From first two statement we have the formula :
X(G)(X(G) - 1)/2
pairs of color in this coloring.X(G)(X(G) - 1) /2
less than equalsm
so we have :