From: "Eric Farmer" <efarmer@math.uiuc.edu>
Newsgroups: sci.math
Subject: Re: Four color theorem
Date: 8 Dec 1998 03:28:48 GMT

Gerry Myerson <gerry@mpce.mq.edu.au> wrote in article
<gerry-0812981413470001@abinitio.mpce.mq.edu.au>...
> In article <01be2230$c3f46160$3f1a7e82@dialup.cso.uiuc.edu>, "Eric
Farmer"
> <efarmer@math.uiuc.edu> wrote:
> 
> > ...you can construct graphs with a given clique number and
> > arbitrarily large chromatic number.
> 
> How do you construct a graph with no triangle and chromatic number, say, 10?
> I don't doubt you, I'm just having trouble seeing how it's done. 

Start with a triangle-free graph G with vertex set V = {v_1, v_2, ...,
v_n}.  Create a supergraph G' by adding vertices u_1, u_2, ..., u_n, and w,
and adding edges so that the neighborhood of u_i is N(u_i) = N(v_i) (so
that the u_i's form an independent set), and the neighborhood of w is all
of the u_i's.  Then G' is also triangle-free, and X(G') = X(G) + 1.

This is Mycielski's construction; there are many others.

Eric Farmer