Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-10T07:30:01.769Z Has data issue: false hasContentIssue false

Zero-Free Intervals for Flow Polynomials of Near-Cubic Graphs

Published online by Cambridge University Press:  04 September 2006

BILL JACKSON
Affiliation:
School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, UK (e-mail: b.jackson@qmul.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let $P(G,t)$ and $F(G,t)$ denote the chromatic and flow polynomials of a graph $G$. G. D. Birkhoff and D C. Lewis showed that, if $G$ is a plane near-triangulation, then the only zeros of $P(G,t)$ in $(-\infty,2]$ are 0, 1 and 2. We will extend their theorem by showing that a stronger result to the dual statement holds for both planar and non-planar graphs: if $G$ is a bridge graph with at most one vertex of degree other than three, then the only zeros of $F(G,t)$ in $(-\infty,\alpha]$ are 1 and 2, where $\alpha\approx 2.225\cdots$ is the real zero in $(2,3)$ of the polynomial $t^4-8t^3+22t^2-28t+17$. In addition we construct a sequence of ‘near-cubic’ graphs whose flow polynomials have zeros converging to $\alpha$ from above.

Information

Type
Paper
Copyright
© 2006 Cambridge University Press