Re: Graph Coloring

O.K., given the clarification you made elsewhere, the statement in
this article should be corrected:

In article <1169472855.806531.16400@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Abid <abidmuslim@xxxxxxxxx> wrote:
Consider an interference graph G.

If S is a set (with at least two elements) of
non-edges of G, then in any minimal coloring for G, at least one pair
of elements of S has same color.

What you mean to say is, "If S is the set of *all* non-edges of G, then..."

And this statement is true even if S has just one element.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.