Density of Chromatic Roots in Minor-Closed Graph Families

Thomas J. Perrett, Carsten Thomassen*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

204 Downloads (Pure)

Abstract

We prove that the roots of the chromatic polynomials of planar graphs are dense in the interval between 32/27 and 4, except possibly in a small interval around Ï„ + 2 where Ï„ is the golden ratio. This interval arises due to a classical result of Tutte, which states that the chromatic polynomial of every planar graph takes a positive value at Ï„ + 2. Our results lead us to conjecture that Ï„ + 2 is the only such number less than 4.
Original languageEnglish
JournalCombinatorics, Probability & Computing
Volume27
Issue number6
Pages (from-to)988-998
ISSN0963-5483
DOIs
Publication statusPublished - 2018

Keywords

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics
  • Graphic methods
  • Chromatic polynomials
  • Golden ratio
  • Planar graph
  • Positive value
  • Graph theory

Cite this