Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-99-03

May 1999

A matrix method for chromatic polynomials

Norman Biggs


The chromatic polynomials of certain families of graphs can be expressed in terms of the eigenspaces of a linear operator. The operator is represented by a matrix, which is referred to here as the compatibility matrix. In this paper complete sets of eigenfunctions are obtained for several related families, and the results are used to provide information about the location of the zeros of the associated chromatic polynomials. A number of uniform features are observed, and these are explained in terms of general properties of the underlying construction.

A compressed (gzip) PostScript file (63 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-99-03, 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)-171-955 7732.
Fax: +44(0)-171-955 6877.
Email: info@maths.lse.ac.uk

Introduction to the CDAM Research Report Series.
CDAM Homepage.