Re: Graph Coloring Problem

dahl@ee.umn.edu (peter boardhead dahl) writes:
>QUESTION: Given a Conflict graph "G" in which the largest clique
> in the graph is of size "k", is the graph "k" colorable?
> (It seems to be true.)


It seems to be false. A counter-example is a ring of 11 elements where
each connects to its neighbor and to its third neighbor, i.e. vertices
1..11, and 1 connects to 11 and 2 (neighbors) and to 9 and 4 (third
neighbors). This graph contains no 3-clique but it obviously not
2-colorable. BTW, it is a nice example for testing coloring algorithms. If
I remember correctly, the simple algorithm "color first the vertex with
most connections to already colored vertices, and among those the one with
most connections to any vertices" fails for this graph although it usually
yields nice results from a heuristic point of view.


Anyhow, the general problem is NP-complete and you should not search for
optimal solutions. For good approximations, first study the literature.
Sorry, I have no references at hand.


Regards,
Helmut
--

Return to the comp.compilers page.
Search the comp.compilers archives again.