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.)


Hi Peter,


I think not. Here's a counter-example.
Look at a string of 4-cliques. I'll draw the basic clique like this


0 - 2
| X |
1 - 3


that is, four vertices: 0, 1, 2, 3
and 6 edges: 0-1, 0-2, 0-3, 1-3, 1-2, 2-3


The string would look like


0 - 2 - 4 - 6 - 8
| X | X | X | X |
1 - 3 - 5 - 7 - 9


Assigning colors (say, a, b, c, and d), we get


a - c - a - c - a
| X | X | X | X |
b - d - b - d - b


which is fine. Now suppose we connect the ends of our string,
creating a new clique, with the edges


0-8, 1-8, 0-9, 1-9


The resulting graph can't be colored in only four colors;
but the largest clique still has only 4 vertices.


Here's the smallest counterexample.


Consider a pentagon.
The largest clique is 2, but it requires 3 colors.


1 - 2
| |
2 1
\ /
3


Of course, it's easy to make larger cases.
All simple cycles with an odd number of vertices require 3 colors,
and in all cases with more than 3 vertices, the largest clique is 2.


Preston Briggs
--

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