Skip to content

CSM

Seminar

Chromatic factorisation of graphs

Morgan, K (Monash)
Monday 21 January 2008, 16:00-16:30

Seminar Room 1, Newton Institute

Abstract

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.

Presentation

[pdf ]

Audio

MP3MP3

Video

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.

Back to top ∧