skip to content

Chromatic factorisation of graphs

Presented by: 
K Morgan [Monash]
Monday 21st January 2008 - 16:00 to 16:30
INI Seminar Room 1

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.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons