Tue, 27 Oct 1992 23:44:46 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) |

[1 later articles] |

Newsgroups: | comp.compilers,comp.theory |

From: | jrbd@craycos.com (James Davies) |

Organization: | Cray Computer Corporation |

Date: | Tue, 27 Oct 1992 23:44:46 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.)*

Well, it took about 100 years to prove this for the specific case k=4, so

don't expect the general proof to be very easy (hint: a planar graph can't

have a clique of size 5 :-).

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.