Centre for Discrete and Applicable Mathematics 

CDAM Research Report, LSECDAM200102July 2001 
Norman Biggs
Abstract
The chromatic polynomials considered in this paper are associated with graphs constructed in the following way. Take n copies of a complete graph K_{b} and, for i = 1, 2,...,n, join each vertex in the ith copy to the same vertex in the (i+1)th copy, taking n+1 = 1 by convention. Previous calculations for b = 2 and b = 3 suggest that the chromatic polynomial contains terms that occur in `levels'. In the present paper the levels are explained by using a version of the sieve principle, and it is shown that the terms at level l correspond to the irreducible representations of the symmetric group Sym_{l}. In the case of the two linear representations the terms can be calculated explicitly by methods based on the theory of distanceregular graphs. For the nonlinear representations the calculations are more complicated. An illustration is given in Section 10, where the complete chromatic polynomial for the case b = 4 is obtained.
A PDF file (199 kB) with the full contents of this report can be downloaded by clicking here.
Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSECDAM200102, together with your name and postal address to:
CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K. 

Phone: +44(0)207955 7732. Fax: +44(0)207955 6877. Email: info@maths.lse.ac.uk 
Introduction to the CDAM Research Report Series.  
CDAM Homepage. 
Last changed: Wed 9 Feb 2005
For comments go to:
http://www.maths.lse.ac.uk/webmaster.html