Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-2001-06

September 2001

Algebraic Methods for Chromatic Polynomials

N. L. Biggs, M. H. Klin, and P. Reinfeld

Abstract

In this paper we discuss the chromatic polynomial of a `bracelet', when the base graph is a complete graph and arbitrary links between the copies are allowed. The resulting graph will be denoted by Ln(b). We show that the chromatic polynomial of Ln(b) can be written in the form

\begin{displaymath}P(L_n(b); k) \; = \; \sum_{\ell =0}^{b} \sum_{\pi \vdash \ell} m_{\pi}(k) \; {\rm tr}(N_L^{\pi})^n.\end{displaymath}

Here the notation $\pi\vdash\ell$ means that $\pi$ is a partition of $\ell$, and $m_{\pi}(k)$ is a polynomial that does not depend on L. The square matrix $N_L^{\pi}$ has size $\binom{b}{\ell}n_{\pi}$, where $n_\pi$ is the degree of the representation $R^{\pi}$ of $Sym_{\ell}$ associated with $\pi$.
We derive an explicit formula for $m_{\pi}(k)$ and describe a method for calculating the matrices $N_L^{\pi}$. Examples are given. Finally, we discuss the application of these results to the problem of locating the chromatic zeros.

A PDF file (182 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-06, 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 2005

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