,
The Largest Real Zero of the Chromatic Polynomial
Discrete Mathematics, 172 (1–3): 141--153 (1997)
DOI: 10.1016/S0012-365X(96)00277-4
Аннотация
It is proved that if every subcontraction of a graph G contains a vertex with degree at most k, then the chromatic polynomial of G is positive throughout the interval (k, ∞); Kk+1 shows that this interval is the largest possible. It is conjectured that the largest real zero of the chromatic polynomial of a χ-chromatic planar graph is always less than χ. For χ = 2 and 3, constructions are given for maximal maximally-connected χ-chromatic planar graphs (i.e., 3-connected quadrangulations for χ = 2 and 4-connected triangulations for χ = 3) whose chromatic polynomials have real zeros arbitrarily close to (but less than) χ.
