%0 Journal Article %1 jackson07 %A Jackson, Bill %D 2007 %J Journal of Combinatorial Theory, Series B %K algebraic.graph.theory chromatic graph.theory polynomial root root-free %N 1 %P 127 -- 143 %R http://dx.doi.org/10.1016/j.jctb.2006.04.006 %T A Zero-Free Interval for Flow Polynomials of Cubic Graphs %V 97 %X Let P ( G , t ) and F ( G , t ) denote the chromatic and flow polynomials of a graph G. Woodall has shown that, if G is a plane triangulation, then the only zeros of P ( G , t ) in ( − ∞ , γ ) are 0, 1 and 2, where γ ≈ 2.54 … is the zero in ( 2 , 3 ) of the chromatic polynomial of the octahedron. The main purpose of this paper is to remove the planarity hypothesis from Woodall's theorem by showing that the dual statement holds for both planar and non-planar graphs: if G is a cubic bridgeless graph, then the only zeros of F ( G , t ) in ( − ∞ , γ ) are 1 and 2, where γ ≈ 2.54 … is the zero in ( 2 , 3 ) of the flow polynomial of the cube. Our inductive proof technique forces us to work with near-cubic graphs, that is to say graphs with minimum degree at least two and at most one vertex of degree greater then three. We also obtain related results concerning the zero distribution of the flow polynomials of near-cubic graphs.

@article{jackson07, abstract = {Let P ( G , t ) and F ( G , t ) denote the chromatic and flow polynomials of a graph G. Woodall has shown that, if G is a plane triangulation, then the only zeros of P ( G , t ) in ( − ∞ , γ ) are 0, 1 and 2, where γ ≈ 2.54 … is the zero in ( 2 , 3 ) of the chromatic polynomial of the octahedron. The main purpose of this paper is to remove the planarity hypothesis from Woodall's theorem by showing that the dual statement holds for both planar and non-planar graphs: if G is a cubic bridgeless graph, then the only zeros of F ( G , t ) in ( − ∞ , γ ) are 1 and 2, where γ ≈ 2.54 … is the zero in ( 2 , 3 ) of the flow polynomial of the cube. Our inductive proof technique forces us to work with near-cubic graphs, that is to say graphs with minimum degree at least two and at most one vertex of degree greater then three. We also obtain related results concerning the zero distribution of the flow polynomials of near-cubic graphs. }, added-at = {2015-05-10T12:52:06.000+0200}, author = {Jackson, Bill}, biburl = {https://www.bibsonomy.org/bibtex/2ea95b83c12cb0f0584f901ac3f4111c3/ytyoun}, doi = {http://dx.doi.org/10.1016/j.jctb.2006.04.006}, interhash = {41e349bfafb811b8cb0843c6d7b0c939}, intrahash = {ea95b83c12cb0f0584f901ac3f4111c3}, issn = {0095-8956}, journal = {Journal of Combinatorial Theory, Series B }, keywords = {algebraic.graph.theory chromatic graph.theory polynomial root root-free}, number = 1, pages = {127 -- 143}, timestamp = {2016-02-28T10:59:36.000+0100}, title = {A Zero-Free Interval for Flow Polynomials of Cubic Graphs }, volume = 97, year = 2007 }