Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1100.05040
Sokal, Alan D.
Chromatic roots are dense in the whole complex plane. (English)
[J] Comb. Probab. Comput. 13, No. 2, 221-261 (2004). ISSN 0963-5483; ISSN 1469-2163/e

The chromatic polynomial was introduced by Birkhoff in 1912. While the original hope was an alternative approach to estimating the chromatic number of a graph, there seems to be no result of that type. Instead, several other properties of the chromatic polynomial have led to interesting results and conjectures, including the distribution of their roots, called the chromatic roots. The present paper is an important contribution to this study. The author, who is also a physicist, first explains why the complex roots of the chromatic polynomials, or, more generally, the Tutte polynomials, are of interest in physics, and then he proves the very surprising result that the chromatic roots of the generalized theta graphs, that is, the graphs consisting of a collection of internally disjoint paths joining the same two vertices, have chromatic roots which are dense in the complex plane except the disc with center $1$ and radius $1$. As the chromatic roots of a graph $G$ can be translated by adding a complete graph joined completely to $G$, it follows that the chromatic roots of all graphs form a dense subset of the complex plane. The author mentions as unsolved if the same holds for the class of planar graphs. He also asks if there are planar graphs with real roots arbitrarily close to $4$. An affirmative answer has recently been announced by Gordon Royle.
[Carsten Thomassen (Lyngby)]

MSC 2000:: *05C15 Chromatic theory of graphs and maps

Keywords: chromatic polynomial; generalized theta graphs

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]