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

Thomas Perrett

Research output: Contribution to journalJournal articleResearchpeer-review

154 Downloads (Pure)

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.
Original languageEnglish
JournalDiscrete Mathematics
Volume339
Issue number11
Pages (from-to)2706-2714
ISSN0012-365X
DOIs
Publication statusPublished - 2016

Keywords

  • Chromatic polynomial
  • Zero-free interval
  • Spanning tree
  • Splitting-closed

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

}

A zero-free interval for chromatic polynomials of graphs with 3-leaf spanning trees. / Perrett, Thomas.

In: Discrete Mathematics, Vol. 339, No. 11, 2016, p. 2706-2714.

Research output: Contribution to journalJournal articleResearchpeer-review

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

VL - 339

SP - 2706

EP - 2714

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 11

ER -