Algebraic methods for chromatic polynomials

In this paper we discuss the chromatic polynomial of a ‘bracelet’, when the base graph is a complete graph Kb and arbitrary links L between the consecutive copies are allowed. If there are n copies of the base graph the resulting graph will be denoted by Ln(b). We show that the chromatic polynomial of Ln(b) can be written in the formP(Ln(b);k)=∑ℓ=0b∑π⊢ℓmπ(k)tr (NLπ)n.Here the notation π⊢ℓ means that π is a partition of ℓ, and mπ(k) is a polynomial that does not depend on L. The square matrix NLπ has size bℓnπ, where nπ is the degree of the representation Rπ of Symℓ associated with π. ive an explicit formula for mπ(k) and describe a method for calculating the matrices NLπ. Examples are given. Finally, we discuss the application of these results to the problem of locating the chromatic zeros.