info prev up next book cdrom email home

Chromatic Polynomial

A Polynomial $P(z)$ of a graph $g$ which counts the number of ways to color $g$ with exactly $z$ colors. Tutte (1970) showed that the chromatic Polynomials of planar triangular graphs possess a Root close to $\phi^2=2.618033\ldots$, where $\phi$ is the Golden Mean. More precisely, if $n$ is the number of Vertices of $G$, then

P_G(\phi^2)\leq \phi^{5-n}

(Le Lionnais 1983).


Le Lionnais, F. Les nombres remarquables. Paris: Hermann, p. 46, 1983.

Tutte, W. T. ``On Chromatic Polynomials and the Golden Ratio.'' J. Combin. Th. 9, 289-296, 1970.

© 1996-9 Eric W. Weisstein