Re: Graph Coloring


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.

I am claiming the first statement. ( which is true)

Thanks
Abid

.