Two chromatic polynomial conjectures

Paul Seymour

doi:10.1006/jctb.1997.1749

Two chromatic polynomial conjectures

Paul Seymour

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

LetP(λ) be the chromatic polynomial of a graph. We show thatP(5)^-1P(6)²P(7)^-1can be arbitrarily small, disproving a conjecture of Welsh (and of Brenti, independently) thatP(λ)²≥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 language	English (US)
Pages (from-to)	184-196
Number of pages	13
Journal	Journal of Combinatorial Theory. Series B
Volume	70
Issue number	1
DOIs	https://doi.org/10.1006/jctb.1997.1749
State	Published - May 1997
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1006/jctb.1997.1749

Cite this

@article{a119f168ee904c48a372fd0cf7acf705,

title = "Two chromatic polynomial conjectures",

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 ...).",

author = "Paul Seymour",

year = "1997",

month = may,

doi = "10.1006/jctb.1997.1749",

language = "English (US)",

volume = "70",

pages = "184--196",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Two chromatic polynomial conjectures

AU - Seymour, Paul

PY - 1997/5

Y1 - 1997/5

N2 - 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 ...).

AB - 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 ...).

UR - http://www.scopus.com/inward/record.url?scp=0031139105&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031139105&partnerID=8YFLogxK

U2 - 10.1006/jctb.1997.1749

DO - 10.1006/jctb.1997.1749

M3 - Article

AN - SCOPUS:0031139105

SN - 0095-8956

VL - 70

SP - 184

EP - 196

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 1

ER -

Two chromatic polynomial conjectures

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this