Re: Graph Coloring Problem

sgall+@CS.CMU.EDU (Jiri Sgall)
Sat, 31 Oct 1992 01:02:17 GMT

          From comp.compilers
Related articles
[2 earlier articles]
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)
| List of all articles for this month |
Newsgroups: comp.compilers,comp.theory
From: sgall+@CS.CMU.EDU (Jiri Sgall)
Organization: Carnegie Mellon University
Date: Sat, 31 Oct 1992 01:02:17 GMT
References: 92-10-093 92-10-107
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?
|>
|> 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 :-).


Obviously this does not prove anything relevant. Being planar is much
stronger property than not having a clique of size 5.


In fact, Erdos in 1959 proved that for any k and l there is a graph that
is not k colorable and does not contain a circle shorter than l. Any
clique contains triangle, i.e. 3-cycle, hence it is trivial consequence
that James' claim is not true for any k.


For the proof see e.g. Alon, Spencer, The Probabilistic Methods, chapter
3. I beleive that there are constructive examples of these graphs, but
the general construction is much more complicated that the probabilistic
proof (as usual).


-- Jiri Sgall
--

Post a followup to this message

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