Re: Graph Coloring Problem

pugh@cs.umd.edu (Bill Pugh)
Tue, 27 Oct 1992 21:03:32 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)
[2 later articles]
| List of all articles for this month |
Newsgroups: comp.compilers,comp.theory
From: pugh@cs.umd.edu (Bill Pugh)
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Date: Tue, 27 Oct 1992 21:03:32 GMT
Followup-To: comp.compilers
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.)


If so, you would have a n^4 algorithm for checking if a graph was
3-colorable, by checking to see if any cliques of size 4 exist.


I don't think so...


Bill Pugh
--

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.