|Graph Coloring Problem email@example.com (1992-10-24)|
|Re: Graph Coloring Problem firstname.lastname@example.org (1992-10-27)|
|Re: Graph Coloring Problem email@example.com (1992-10-27)|
|Re: Graph Coloring Problem firstname.lastname@example.org (1992-10-28)|
|Re: Graph Coloring Problem Richter@lrz.lrz-muenchen.dbp.de (1992-10-28)|
|Re: Graph Coloring Problem email@example.com (1992-10-28)|
|Re: Graph Coloring Problem firstname.lastname@example.org (1992-10-28)|
|Re: Graph Coloring Problem email@example.com (1992-10-30)|
|Re: Graph Coloring Problem sgall+@CS.CMU.EDU (1992-10-31)|
|Re: Graph Coloring Problem firstname.lastname@example.org (1992-11-06)|
|From:||email@example.com (Preston Briggs)|
|Organization:||Rice University, Houston|
|Date:||Fri, 30 Oct 1992 01:16:06 GMT|
firstname.lastname@example.org (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.)
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
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.
Return to the
Search the comp.compilers archives again.