A zero-free interval for chromatic polynomials of graphs with 3-leaf spanning trees

Thomas Perrett

doi:10.1016/j.disc.2016.05.009

A zero-free interval for chromatic polynomials of graphs with 3-leaf spanning trees

Thomas Perrett

Department of Applied Mathematics and Computer Science

Research output: Contribution to journal › Journal article › Research › peer-review

396 Downloads (Orbit)

Abstract

It is proved that if G is a graph containing a spanning tree with at most three leaves, then the chromatic polynomial of G has no roots in the interval (1,t1], where t1≈1.2904 is the smallest real root of the polynomial (t-2)⁶+4(t-1)² (t-2)³-(t-1)⁴. We also construct a family of graphs containing such spanning trees with chromatic roots converging to t1 from above. We employ the Whitney 2-switch operation to manage the analysis of an infinite class of chromatic polynomials.

Original language	English
Journal	Discrete Mathematics
Volume	339
Issue number	11
Pages (from-to)	2706-2714
ISSN	0012-365X
DOIs	https://doi.org/10.1016/j.disc.2016.05.009
Publication status	Published - 2016

Keywords

Chromatic polynomial
Zero-free interval
Spanning tree
Splitting-closed

Access to Document

10.1016/j.disc.2016.05.009

Zero freeAccepted author manuscript, 274 KB

OpenUrl availability

Check availability in DTU Findit

Cite this

@article{5e37f86bd0b246f88d93a62b3208ce39,

title = "A zero-free interval for chromatic polynomials of graphs with 3-leaf spanning trees",

abstract = "It is proved that if G is a graph containing a spanning tree with at most three leaves, then the chromatic polynomial of G has no roots in the interval (1,t1], where t1≈1.2904 is the smallest real root of the polynomial (t-2)6+4(t-1)2 (t-2)3-(t-1)4. We also construct a family of graphs containing such spanning trees with chromatic roots converging to t1 from above. We employ the Whitney 2-switch operation to manage the analysis of an infinite class of chromatic polynomials.",

keywords = "Chromatic polynomial, Zero-free interval, Spanning tree, Splitting-closed",

author = "Thomas Perrett",

year = "2016",

doi = "10.1016/j.disc.2016.05.009",

language = "English",

volume = "339",

pages = "2706--2714",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "11",

}

TY - JOUR

T1 - A zero-free interval for chromatic polynomials of graphs with 3-leaf spanning trees

AU - Perrett, Thomas

PY - 2016

Y1 - 2016

N2 - It is proved that if G is a graph containing a spanning tree with at most three leaves, then the chromatic polynomial of G has no roots in the interval (1,t1], where t1≈1.2904 is the smallest real root of the polynomial (t-2)6+4(t-1)2 (t-2)3-(t-1)4. We also construct a family of graphs containing such spanning trees with chromatic roots converging to t1 from above. We employ the Whitney 2-switch operation to manage the analysis of an infinite class of chromatic polynomials.

AB - It is proved that if G is a graph containing a spanning tree with at most three leaves, then the chromatic polynomial of G has no roots in the interval (1,t1], where t1≈1.2904 is the smallest real root of the polynomial (t-2)6+4(t-1)2 (t-2)3-(t-1)4. We also construct a family of graphs containing such spanning trees with chromatic roots converging to t1 from above. We employ the Whitney 2-switch operation to manage the analysis of an infinite class of chromatic polynomials.

KW - Chromatic polynomial

KW - Zero-free interval

KW - Spanning tree

KW - Splitting-closed

U2 - 10.1016/j.disc.2016.05.009

DO - 10.1016/j.disc.2016.05.009

M3 - Journal article

SN - 0012-365X

VL - 339

SP - 2706

EP - 2714

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 11

ER -

A zero-free interval for chromatic polynomials of graphs with 3-leaf spanning trees

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this