Re: Graph Coloring

Abid wrote:
1--If there are more than one pairs of nodes that donot have edges
between them , then atleast one pair will have same color.

In article <1169360194.777407.14610@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Proginoskes <CCHeckman@xxxxxxxxx> wrote:
That's not how I interpretted the problem. In my interpretation, you
choose the two non-edges first, then the coloring.

Oh, I see. You mean, "If S is a set (with at least two elements) of
non-edges, then in any minimal coloring, at least one member of S is
monochromatic." That's certainly false.

I guess we have to ask Abid what was intended.
--
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
.