tr-2008-222-full.pdf (294.8 kB)

# Chromatic Factorisations

report

posted on 2022-07-25, 00:26 authored by K Morgan, G FarrThe chromatic polynomial gives the number of proper λ-colourings of, a graph G. This paper considers factorisation of the chromatic polynomial as a first step in an algebraic study of the roots of this polynomial. The chromatic polynomial of a graph is said to have a chromatic factorisation if P(G, λ) = P(H

_{1}, λ) P(H_{2},λ)/P(K_{r}, λ) for some graphs H_{1}and H_{2}and clique K_{r}. It is known that the chromatic polynomial of any clique-separable graph, that is, a graph containing a separating r-clique, has a chromatic factorisation. We show that there exist other chromatic polynomials that have chromatic factorisations but are not the chromatic polynomial of any clique-separable graph and identify all such chromatic polynomials of degree at most 10. We introduce the notion of a certificate of factorisation, which provides an explanation for such a factorisation, and find certificates for all cases of degree ≤ 9. The lengths of these certificates are less than an upper bound we establish of ≤ n22 n2/2). Furthermore, we construct an infinite family of non-clique-separable graphs that have chromatic factorisations and give certificates of factorisation for graphs belonging to this family.