Re: Graph Coloring

Hello:
First Thank you again for this discussion. I am working on a heuristic
for register allocation problem in a compiler. I think, the following
statement is what I intended:
------------------------------
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.


( I rephrased Tim's Statement
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.)
------------------------------

Thanks
Abid

.

Relevant Pages

  • Re: Graph Coloring
    ... for register allocation problem in a compiler. ... triangle and an additional node not connected to the triangle. ... Then S is a set of non-edges with at least two ...
    (comp.theory)
  • Re: Graph Coloring
    ... Your two most recent responses seem to contradict each other, ... For concreteness, let's suppose G has five non-edges, which ... In any minimal coloring of G, at least one of the five non-edges ...
    (comp.theory)