Wed, 28 Oct 1992 08:24:36 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) |

Re: Graph Coloring Problem kuzemcha@tartan.com (1992-11-06) |

Newsgroups: | comp.compilers,comp.theory |

From: | Richter@lrz.lrz-muenchen.dbp.de |

Organization: | Leibniz-Rechenzentrum, Muenchen (Germany) |

Date: | Wed, 28 Oct 1992 08:24:36 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?*

*> (It seems to be true.)*

It seems to be false. A counter-example is a ring of 11 elements where

each connects to its neighbor and to its third neighbor, i.e. vertices

1..11, and 1 connects to 11 and 2 (neighbors) and to 9 and 4 (third

neighbors). This graph contains no 3-clique but it obviously not

2-colorable. BTW, it is a nice example for testing coloring algorithms. If

I remember correctly, the simple algorithm "color first the vertex with

most connections to already colored vertices, and among those the one with

most connections to any vertices" fails for this graph although it usually

yields nice results from a heuristic point of view.

Anyhow, the general problem is NP-complete and you should not search for

optimal solutions. For good approximations, first study the literature.

Sorry, I have no references at hand.

Regards,

Helmut

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.