zbMATH — the first resource for mathematics

Density of real zeros of the Tutte polynomial. (English) Zbl 1388.05093
Summary: The Tutte polynomial of a graph is a two-variable polynomial whose zeros and evaluations encode many interesting properties of the graph. In this article we investigate the real zeros of the Tutte polynomials of graphs, and show that they form a dense subset of certain regions of the plane. This is the first density result for the real zeros of the Tutte polynomial in a region of positive volume. Our result almost confirms a conjecture of B. Jackson and A. D. Sokal [J. Comb. Theory, Ser. B 99, No. 6, 869–903 (2009; Zbl 1221.05144)] except for one region which is related to an open problem on flow polynomials.

05C31 Graph polynomials
Full Text: DOI
[1] Dong, F. M. and Jackson, B. (2011) A zero-free interval for chromatic polynomials of nearly 3-connected plane graphs. SIAM J. Discrete Math.251103-1118. doi:10.1137/100790057 · Zbl 1237.05051
[2] Goldberg, L. A. and Jerrum, M. (2008) Inapproximability of the Tutte polynomial. Inform. Comput.206908-929. doi:10.1016/j.ic.2008.04.003 · Zbl 1153.68039
[3] Goldberg, L. A. and Jerrum, M. (2012) Inapproximability of the Tutte polynomial of a planar graph. Comput. Complexity21605-642. doi:10.1007/s00037-012-0046-4 · Zbl 1282.68122
[4] Goldberg, L. and Jerrum, M. (2014) The complexity of computing the sign of the Tutte polynomial. SIAM J. Comput.431921-1952. doi:10.1137/12088330X
[5] Jackson, B., A zero-free interval for chromatic polynomials of graphs, Combin. Probab. Comput., 2, 325-336, (1993) · Zbl 0794.05030
[6] Jackson, B. and Sokal, A. (2009) Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids. J. Combin. Theory Ser. B99869-903. doi:10.1016/j.jctb.2009.03.002 · Zbl 1221.05144
[7] Jacobsen, J. and Salas, J. (2013) Is the five-flow conjecture almost false?J. Combin. Theory Ser. B103532-565. doi:10.1016/j.jctb.2013.06.001 · Zbl 1301.05153
[8] Jaeger, F., Vertigan, D. L. and Welsh, D. J. A. (1990) On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Philos. Soc.10835-53. doi:10.1017/S0305004100068936 · Zbl 0747.57006
[9] Royle, G. and Sokal, A. (2015) Linear bound in terms of maxmaxflow for the chromatic roots of series-parallel graphs. SIAM J. Discrete Math.292117-2159. doi:10.1137/130930133 · Zbl 1323.05071
[10] Sokal, A., Chromatic roots are dense in the whole complex plane, Combin. Probab. Comput., 13, 221-261, (2004) · Zbl 1100.05040
[11] Sokal, A. (2005) The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. In Surveys in Combinatorics, 2005 (Webb, B., ed.), Cambridge University Press, pp. 173-226. doi:10.1017/CBO9780511734885 · Zbl 1110.05020
[12] Thomassen, C., The zero-free intervals for chromatic polynomials of graphs, Combin. Probab. Comput., 6, 497-506, (1997) · Zbl 0887.05020
[13] Tutte, W. (1974) Chromials. In Hypergraph Seminar (Berge, C. and Ray-Chaudhuri, D., eds), Vol. 411 of Lecture Notes in Mathematics, Springer, pp. 243-266. doi:10.1007/BFb0066173
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.