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?


Answer: NO.


If every vertex in clique Q EXCEPT one touches a vertex R not in the
clique, then R's color is fixed. If clique Q is involved in k such
vertices R1..Rk, each of those vertices can have their color fixed to the
k different colors in Q. Finally, connect a vertex S to each of the R
vertices. S touches all k colors and so requires another color, but the
largest clique is of size k.


Here is a counter example for k=3:




              R1-----A-----R2-------\ to R1
                \ / \ / \ |
                  \ / Q \ / \ /
                B \/_____\/ C S---/
                      \ / /
                        \ / /
                          \ / /
                            R3------------/


Here clique Q impinges on vertices R1, R2 and R3.
If A, B and C are colors, then
R1 must be color C,
R2 must be color B,
R3 must be color A.
S touches colors A, B and C and so must be a 4th color D.
There is no 4 clique (by inspection).


Cliff Click (cliffc@cs.rice.edu)
--

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