|Graph Coloring Problem firstname.lastname@example.org (1992-10-24)|
|Re: Graph Coloring Problem email@example.com (1992-10-27)|
|Re: Graph Coloring Problem firstname.lastname@example.org (1992-10-27)|
|Re: Graph Coloring Problem email@example.com (1992-10-28)|
|Re: Graph Coloring Problem Richter@lrz.lrz-muenchen.dbp.de (1992-10-28)|
|Re: Graph Coloring Problem firstname.lastname@example.org (1992-10-28)|
|Re: Graph Coloring Problem email@example.com (1992-10-28)|
|Re: Graph Coloring Problem firstname.lastname@example.org (1992-10-30)|
|Re: Graph Coloring Problem sgall+@CS.CMU.EDU (1992-10-31)|
|Color Permutation Problem email@example.com (1992-11-05)|
|Re: Graph Coloring Problem firstname.lastname@example.org (1992-11-06)|
|From:||email@example.com (Cliff Click)|
|Organization:||Center for Research on Parallel Computations|
|Date:||Wed, 28 Oct 1992 15:20:14 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?
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---/
\ / /
\ / /
\ / /
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 (email@example.com)
Return to the
Search the comp.compilers archives again.