Two chromatic polynomial conjectures

Research output: Contribution to journalArticle

7 Scopus citations

Abstract

LetP(λ) be the chromatic polynomial of a graph. We show thatP(5)-1P(6)2P(7)-1can be arbitrarily small, disproving a conjecture of Welsh (and of Brenti, independently) thatP(λ)2≥P(λ-1)P(λ+1)and also disproving several other conjectures of Brenti. Secondly, we prove that if the graph has n vertices, thenP(n)P(n-1)-1≥2.718253,approaching a conjecture of Bartels and Welsh thatP(n)P(n-1)-1≥e(eis 2.718281 ...).

Original languageEnglish (US)
Pages (from-to)184-196
Number of pages13
JournalJournal of Combinatorial Theory. Series B
Volume70
Issue number1
DOIs
StatePublished - May 1 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Two chromatic polynomial conjectures'. Together they form a unique fingerprint.

  • Cite this