Re: Graph Coloring

In article <1169478350.299722.83680@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Abid <abidmuslim@xxxxxxxxx> wrote:
When I say pair, I mean a pair of nodes and not pair of esges. I think
claim is true for a pair of nodes. In your example <v5,v1> and <v3,v2>
are two pairs of nodes with same color.

Your two most recent responses seem to contradict each other, so I think
there is still some miscommunication going on.

Let me try to highlight as clearly as possible the important distinction
that is being made here. Suppose we have a graph G with at least two
non-edges. For concreteness, let's suppose G has five non-edges, which
we'll call p_1, p_2, p_3, p_4, p_5. Which of the following do you claim
to be true?

1. In any minimal coloring of G, at least one of the five non-edges
p_1, p_2, p_3, p_4, p_5 will be monochromatic (i.e., the two vertices
are assigned the same color).

2. I can pick *any* subset S of non-edges, as long as S has at least
two elements (for example, I could choose S = {p_2, p_4, p_5}),
and in any minimal coloring of G, at least one of the members of S
will be monochromatic.

1 is true, and 2 is false.
--
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
.