skip to content

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

Presented by: 
FM Dong [Nanyang Technological]
Tuesday 22nd January 2008 - 14:00 to 15:00
INI Seminar Room 1

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).

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