# Re: Graph Coloring Problem

## cliffc@rice.edu (Cliff Click)Wed, 28 Oct 1992 15:20:14 GMT

From comp.compilers

Related articles
Graph Coloring Problem dahl@ee.umn.edu (1992-10-24)
Re: Graph Coloring Problem pugh@cs.umd.edu (1992-10-27)
Re: Graph Coloring Problem jrbd@craycos.com (1992-10-27)
Re: Graph Coloring Problem pat%frumious.uucp@uunet.ca (1992-10-28)
Re: Graph Coloring Problem Richter@lrz.lrz-muenchen.dbp.de (1992-10-28)
Re: Graph Coloring Problem cliffc@rice.edu (1992-10-28)
Re: Graph Coloring Problem moss@cs.umass.edu (1992-10-28)
Re: Graph Coloring Problem preston@cs.rice.edu (1992-10-30)
Re: Graph Coloring Problem sgall+@CS.CMU.EDU (1992-10-31)
Color Permutation Problem jdcho@karachi.eecs.nwu.edu (1992-11-05)
Re: Graph Coloring Problem kuzemcha@tartan.com (1992-11-06)
| List of all articles for this month |

 Newsgroups: comp.compilers,comp.theory From: cliffc@rice.edu (Cliff Click) Organization: Center for Research on Parallel Computations Date: Wed, 28 Oct 1992 15:20:14 GMT References: 92-10-093 Keywords: theory

> 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---/
\ / /
\ / /
\ / /
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)
--

Post a followup to this message