Abstract :
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) χ.
