The largest real zero of the chromatic polynomial

✍ Scribed by D.R. Woodall

• Book ID: 104113789
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 507 KB
• Volume: 172
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(96)00277-4

✦ Synopsis

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, c~); Kk+l shows that this interval is the largest possible. It is conjectured that the largest real zero of the chromatic polynomial of a z-chromatic planar graph is always less than X. For Z = 2 and 3, constructions are given for maximal maximally-connected Z-chromatic planar graphs (i.e., 3-connected quadrangulations for ~ = 2 and 4-connected triangulations for Z = 3) whose chromatic polynomials have real zeros arbitrarily close to (but less than) X.