From: tim_brooks@my-deja.com
Subject: Cayley graphs and chromatic number
Date: Tue, 16 Jan 2001 05:46:10 GMT
Newsgroups: sci.math
Summary: Bounding the chromatic number of Cayley graphs with Brooks' theorem

Let G be a finite group with n elements and x1,x2,...xm a minimal set
of generators of G i.e x1,x2,...,xm generates G and any set of
generators of G has at least m elements.
Is there some bound on the chromatic number of the
Cayley graph associated with x1,x2,...,xm ?
a bound that uses n and m ?

Thanks,
Tim


Sent via Deja.com
http://www.deja.com/
==============================================================================

From: David Eppstein <eppstein@ics.uci.edu>
Subject: Re: Cayley graphs and chromatic number
Date: Tue, 16 Jan 2001 08:17:50 -0800
Newsgroups: sci.math

In article <940r4t$o9$1@nnrp1.deja.com>, tim_brooks@my-deja.com wrote:

> This is strange, by my last name I should know Brooks theorem :-).
> Can you tell me what the theorem says ? I am not familiar with it.

Any graph with maximum degree k that is not a clique or odd cycle has 
chromatic number at most k.  Cayley graphs with m generators have degree at 
most 2m so I guess this means that, with the exception of odd cyclic 
groups, finite Cayley graphs for minimal generator sets are at most 
2m-chromatic.
-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/