# Re: Graph Coloring Problem

## Richter@lrz.lrz-muenchen.dbp.deWed, 28 Oct 1992 08:24:36 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)
Re: Graph Coloring Problem kuzemcha@tartan.com (1992-11-06)
| List of all articles for this month |

 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

>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