On graphs whose chromatic polynomials have no zeros in (1,2)

1 hour 41 secs, 839.43 MB, MPEG-4 Video 480x360, 25.0 fps, 44100 Hz, 1.84 Mbits/sec

About this item

Description:	Dong, FM (Nanyang Technological ) Tuesday 22 January 2008, 14:00-15:00 Zeros of Graph Polynomials

Created:

2008-01-31 15:42

Collection:

Combinatorics and Statistical Mechanics

Publisher:

Isaac Newton Institute

Dong, FM

Language:

eng (English)

Credits:

Author:

Dong, FM


Abstract:	The study of zero distribution of chromatic polynomials has attracted the attention of researchers working in both Mathematics and Physics. In this talk, I shall focus on the study of graphs which have no chromatic zeros in (1, 2). One of the motivations of this study is to find some useful methods to attack the famous conjecture that every plane graph has no chromatic zeros in (4, 5). Due to Jackson’s and Thomassen’s results, it is now confirmed that there are only three maximal intervals (-?, 0), (0, 1) and (1, 32/27], in which all chromatic polynomials are zero-free. Jackson conjectured in 1993 that every 3-connected non-bipartite graph has no chromatic zeros in (1, 2). It was recently disproved by Royle’s discovery of some counter-examples. However, Jackson’s conjecture triggered the study of graphs which have no chromatic zeros in (1, 2). Let F be the family of K2 and 2-connected graphs which have no chromatic zeros in (1, 2). We can show that this family is ‘closed’ in some senses under certain operations. Applying this result, we are able to find some subfamilies of graphs which have no chromatic zeros in (1, 2). A connected graph G is said to be ?-tough if the number of components of G - S is at most Sfor all non-empty independent sets S in G. We observed that, up to now, all 2-connected graphs in F that have been discovered are ?-tough. Based on this observation, we conjectured that every ?-tough graph belongs to F. The condition for this conjecture is weaker than that in Thomassen’s conjecture: every Hamiltonian graph contains no chromatic zeros in (1, 2). Finally we shall consider non-?-tough graphs that do have chromatic zeros in (1, 2).

Abstract:

The study of zero distribution of chromatic polynomials has attracted the attention of researchers working in both Mathematics and Physics. In this talk, I shall focus on the study of graphs which have no chromatic zeros in (1, 2). One of the motivations of this study is to find some useful methods to attack the famous conjecture that every plane graph has no chromatic zeros in (4, 5).

Due to Jackson’s and Thomassen’s results, it is now confirmed that there are only three maximal intervals (-?, 0), (0, 1) and (1, 32/27], in which all chromatic polynomials are zero-free. Jackson conjectured in 1993 that every 3-connected non-bipartite graph has no chromatic zeros in (1, 2). It was recently disproved by Royle’s discovery of some counter-examples. However, Jackson’s conjecture triggered the study of graphs which have no chromatic zeros in (1, 2).

Let F be the family of K2 and 2-connected graphs which have no chromatic zeros in (1, 2). We can show that this family is ‘closed’ in some senses under certain operations. Applying this result, we are able to find some subfamilies of graphs which have no chromatic zeros in (1, 2).

A connected graph G is said to be ?-tough if the number of components of G - S is at most Sfor all non-empty independent sets S in G. We observed that, up to now, all 2-connected graphs in F that have been discovered are ?-tough. Based on this observation, we conjectured that every ?-tough graph belongs to F. The condition for this conjecture is weaker than that in Thomassen’s conjecture: every Hamiltonian graph contains no chromatic zeros in (1, 2).

Finally we shall consider non-?-tough graphs that do have chromatic zeros in (1, 2).

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video *	480x360	1.84 Mbits/sec	839.43 MB	View	Download
Flash Video	480x360	806.69 kbits/sec	359.03 MB	View	Download
iPod Video	480x360	505.31 kbits/sec	224.90 MB	View	Download
Windows Media Video (for download)	480x360	477.56 kbits/sec	212.55 MB	View	Download
Windows Media Video (for streaming)	480x360	446.76 kbits/sec	198.84 MB	View	Download	Stream
RealMedia	480x360	878.54 kbits/sec	391.01 MB	View	Download	Stream
QuickTime (for download)	384x288	848.78 kbits/sec	377.77 MB	View	Download
QuickTime (for streaming)	480x360	907.43 kbits/sec	403.87 MB	View	Download
MP3	44100 Hz	125.03 kbits/sec	55.43 MB	Listen	Download