Wed, 28 Oct 1992 18:42:53 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: | moss@cs.umass.edu (Eliot Moss) |

Organization: | Dept of Comp and Info Sci, Univ of Mass (Amherst) |

Date: | Wed, 28 Oct 1992 18:42:53 GMT |

References: | 92-10-093 |

Keywords: | theory |

It is not true that the chromatic number of a graph of maximum clique size

k is exactly k. I exhibit a class of graphs with max clique size k and

chromatic number greater than k, constructed as follows:

Nodes: A1, ..., Ak

B1, ..., Bk,

C11, C12, ..., Ckk for all i and i in [1..k]

Edges: {Ai,Aj} for i not equal to j, i.e., the Ai are a k clique

{Bi,Bj} likewise (the Bi are a k clique)

{Bi,Cij} for all i and j

{Aj,Cik} for all i, and all k EXCEPT j

Coloring: Suppose we color Ai with ai, for i in [1..k]. Then Cij must have

color ai or else a new color. If we use ai on each Cij, then no Bj can use

ai. If we carry this to its conclusion, we end up with 2k colors. On the

other hand, if we use a new color c on all the Cij, we can color the Bi

with the ai colors and thus we see that the chromatic number is k+1.

Granted this is a bit contrived, but it serves to show your proposition is

false. Sorry about that!

--

J. Eliot B. Moss, Associate Professor Visiting Associate Professor

Department of Computer Science School of Computer Science

Lederle Graduate Research Center Carnegie Mellon University

University of Massachusetts 5000 Forbes Avenue

Amherst, MA 01003 Pittsburgh, PA 15213-3891

(413) 545-4206, 545-1249 (fax) (412) 268-6767, 681-5739 (fax)

Moss@cs.umass.edu Moss@cs.cmu.edu

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.