Chromatic factorisation of graphs
Seminar Room 1, Newton Institute
We consider 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(H1,?)P(H2,?)/P(Kr ,?) for some graphs H1 and H2 and clique Kr . It is known that the chromatic polynomial of any cliqueseparable graph, that is, a graph containing a separating rclique, has a chromatic factorisation. We show that there exist other chromatic polynomials that have chromatic factorisations but are not the chromatic polynomial of any cliqueseparable 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 factorisations, and find certificates for all cases of degree ? 9. These certificates are much shorter than the upper bound of O(n 22n/2). Furthermore, we construct an infinite family of noncliqueseparable graphs that have chromatic factorisations and give certificates of factorisation for graphs belonging to this family.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.