Tue, 27 Oct 1992 21:03:32 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) |

[2 later articles] |

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.