Centre for Discrete and Applicable Mathematics |
|
CDAM Research Report, LSE-CDAM-2003-12July 2003 |
Philipp Reinfeld
Abstract
The chromatic polynomials of certain families
of graphs can be calculated by a transfer matrix method. The
transfer matrix commutes with an action of the symmetric group on
the colours. Using representation theory, it is shown that the
matrix is equivalent to a block-diagonal matrix. The
multiplicities and the sizes of the blocks are obtained.
Using a repeated inclusion-exclusion argument the entries of the
blocks can be calculated. In particular, from one of the
inclusion-exclusion arguments it follows that the transfer matrix
can be written as a linear combination of operators which, in
certain cases, form an algebra. The eigenvalues of the blocks can
be inferred from this structure.
The form of the chromatic polynomials permits the use of a theorem
by Beraha, Kahane and Weiss to determine the limiting behaviour of
the roots. The theorem says that, apart from some isolated points,
the roots approach certain curves in the complex plane. Some
improvements have been made in the methods of calculating these
curves.
Many examples are discussed in detail. In particular the chromatic
polynomials of the family of the so-called generalized dodecahedra
and four similar families of cubic graphs are obtained, and the
limiting behaviour of their roots is discussed.
A PDF file (2.2 MB) with the full contents of this report can be downloaded by clicking here.
Because of its size (184 pages), this report is only available electronically.
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