Re: Graph Coloring

Abid wrote:
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 don't think that version is true. Suppose G has vertex set {v1,v2,v3,v4} and edge set {{v1,v2},{v2,v3},{v3,v1}}. That is, G has a triangle and an additional node not connected to the triangle.

Let S={{v1,v4},{v2,v4}}. Then S is a set of non-edges with at least two elements. Consider the coloring (v1,c1),{v2,c2},(v3,c3},(v4,c3}. That is, it assigns distinct colors to the nodes in the triangle, and the same color as v3 to v4.

Then neither edge in S has the same color for both nodes.

Patricia
.

Relevant Pages

  • Re: Graph Coloring
    ... for register allocation problem in a compiler. ... non-edges of G, then in any minimal coloring for G, at least one pair ...
    (comp.theory)
  • Re: Fortran to C to Fortran Arrays
    ... and was replaced by the much cleaner Fortran 77 '*'. ... storing the other triangle. ... It can be done, and any compiler developer ... push the corner cases on the subscript checking. ...
    (comp.lang.fortran)
  • newbie needs help
    ... Compiler: MS Visual C++ 2005 Express Edition ... Calculate the area of a circle6. ... Calculate the third leg of a triangle (Pythagorean ...
    (comp.programming.threads)
  • newbie needs help
    ... Compiler: MS Visual C++ 2005 Express Edition ... Calculate the area of a circle6. ... Calculate the third leg of a triangle (Pythagorean ...
    (comp.programming.threads)