Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-2001-02 July 2001

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 distance-regular 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, LSE-CDAM-2001-02, 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)-20-7955 7732. Fax: +44(0)-20-7955 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