Chromatic factorisation of graphs

33 mins 7 secs, 458.13 MB, MPEG-4 Video 480x360, 25.0 fps, 44100 Hz, 1.84 Mbits/sec

About this item

Description:	Morgan, K (Monash) Monday 21 January 2008, 16:00-16:30 Zeros of Graph Polynomials

Created:

2008-01-31 06:40

Collection:

Combinatorics and Statistical Mechanics

Publisher:

Isaac Newton Institute

Morgan, K

Language:

eng (English)

Credits:

Author:

Morgan, K


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.

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.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video *	480x360	1.84 Mbits/sec	458.13 MB	View	Download
Flash Video	480x360	805.29 kbits/sec	195.92 MB	View	Download
iPod Video	480x360	505.08 kbits/sec	122.88 MB	View	Download
Windows Media Video (for download)	480x360	477.95 kbits/sec	116.28 MB	View	Download
Windows Media Video (for streaming)	480x360	446.74 kbits/sec	108.69 MB	View	Download	Stream
RealMedia	480x360	877.61 kbits/sec	213.51 MB	View	Download	Stream
QuickTime (for download)	384x288	847.95 kbits/sec	206.30 MB	View	Download
QuickTime (for streaming)	480x360	906.61 kbits/sec	220.57 MB	View	Download
MP3	44100 Hz	125.01 kbits/sec	30.20 MB	Listen	Download