Re: Graph Coloring Problem

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
--

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