Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-2000-04

May 2000

A matrix method for chromatic polynomials - II

Norman Biggs


The subject of this paper is the calculation of the chromatic polynomials of graphs that have cyclic symmetry. There are two basic steps. First, a compatibility operator  T  is defined, and a sieve formula for its action is established. Then it is shown that in certain circumstances it is possible to use this formula to construct invariant subspaces for  T.  The resulting eigenvalues and their multiplicities determine terms of the chromatic polynomial, and these terms have special significance in the study of the critical behaviour of physical processes.

The scope of the method is illustrated by three applications. In each case explicit results are obtained and used to provide information about the location of the complex zeros of the chromatic polynomial.

A compressed (gzip) PostScript file (86 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you like a free hard copy of this report, please send the number of this report, LSE-CDAM-2000-04, 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.

Copyright © London School of Economics & Political Science 2000

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html.