|[2 earlier articles]|
|Re: Graph Coloring Problem firstname.lastname@example.org (1992-10-27)|
|Re: Graph Coloring Problem email@example.com (1992-10-28)|
|Re: Graph Coloring Problem Richter@lrz.lrz-muenchen.dbp.de (1992-10-28)|
|Re: Graph Coloring Problem firstname.lastname@example.org (1992-10-28)|
|Re: Graph Coloring Problem email@example.com (1992-10-28)|
|Re: Graph Coloring Problem firstname.lastname@example.org (1992-10-30)|
|Re: Graph Coloring Problem sgall+@CS.CMU.EDU (1992-10-31)|
|Re: Graph Coloring Problem email@example.com (1992-11-06)|
|From:||sgall+@CS.CMU.EDU (Jiri Sgall)|
|Organization:||Carnegie Mellon University|
|Date:||Sat, 31 Oct 1992 01:02:17 GMT|
|> >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
Return to the
Search the comp.compilers archives again.