Wed, 28 Oct 1992 15:20:14 GMT

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

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 |

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)

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.