Linear bound in terms of maxmaxflow for the chromatic roots of series-parallel graphs. (English) Zbl 1323.05071
Summary: We prove that the (real or complex) chromatic roots of a series-parallel graph with maxmaxflow \(\Lambda\) lie in the disc \(|q-1| < (\Lambda-1)/\log 2\). More generally, the same bound holds for the (real or complex) roots of the multivariate Tutte polynomial when the edge weights lie in the “real antiferromagnetic regime” \(-1 \leq v_e \leq 0\). For each \(\Lambda \geq 3\), we exhibit a family of graphs, namely, the “leaf-joined trees”, with maxmaxflow \(\Lambda\) and chromatic roots accumulating densely on the circle \(|q-1|=\Lambda -1\), thereby showing that our result is within a factor \(1/\log 2 \approx 1.442695\) of being sharp.
MSC:
| 05C31 | Graph polynomials |
| 05A20 | Combinatorial inequalities |
| 05C15 | Coloring of graphs and hypergraphs |
| 05C21 | Flows in graphs |
| 05E99 | Algebraic combinatorics |
| 30C15 | Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) |
| 37F10 | Dynamics of complex polynomials, rational maps, entire and meromorphic functions; Fatou and Julia sets |
| 37F45 | Holomorphic families of dynamical systems; the Mandelbrot set; bifurcations (MSC2010) |
| 82B20 | Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics |
Keywords:
chromatic polynomial; multivariate Tutte polynomial; antiferromagnetic Potts model; chromatic roots; maxmaxflow; series-parallel graphReferences:
| [1] | M.W. Bern, E.L. Lawler, and A.L. Wong, {\it Linear-time computation of optimal subgraphs of decomposable graphs}, J. Algorithms, 8 (1987), pp. 216-235. · Zbl 0618.68058 |
| [2] | N.L. Biggs, R.M. Damerell, and D.A. Sands, {\it Recursive families of graphs}, J. Combin. Theory Ser. B, 12 (1972), pp. 123-131. · Zbl 0215.05504 |
| [3] | G.D. Birkhoff and D.C. Lewis, {\it Chromatic polynomials}, Trans. Amer. Math. Soc., 60 (1946), pp. 355-451. · Zbl 0060.41601 |
| [4] | H.L. Bodlaender and B. van Antwerpen-de Fluiter, {\it Parallel algorithms for series parallel graphs and graphs with treewidth two}, Algorithmica, 29 (2001), pp. 534-559. · Zbl 0979.05095 |
| [5] | C. Borgs, {\it Absence of zeros for the chromatic polynomial of bounded degree graphs}, Combin. Probab. Comput., 15 (2006), pp. 63-74. · Zbl 1082.05034 |
| [6] | R.B. Borie, R.G. Parker, and C.A. Tovey, {\it Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families}, Algorithmica, 7 (1992), pp. 555-581. · Zbl 0753.05062 |
| [7] | A. Brandstädt, V.B. Le, and J.P. Spinrad, {\it Graph Classes: A Survey}, Discrete Math. Appl., SIAM, Philadelphia, 1999. · Zbl 0919.05001 |
| [8] | J.V. Brawley, S. Gao, and D. Mills, {\it Associative rational functions in two variables}, in Finite Fields and Applications, D. Jungnickel and H. Niederreiter, eds., Springer-Verlag, Berlin, 2001, pp. 43-56. · Zbl 1007.14004 |
| [9] | F. Brenti, G.F. Royle, and D.G. Wagner, {\it Location of zeros of chromatic and related polynomials of graphs}, Canad. J. Math., 46 (1994), pp. 55-80. · Zbl 0804.05034 |
| [10] | C.J. Colbourn, {\it The Combinatorics of Network Reliability}, Clarendon Press/Oxford University Press, New York, 1987. |
| [11] | R.M. Corless, G.H. Gonnet, D.E.G. Hare, D.J. Jeffrey, and D.E. Knuth, {\it On the Lambert \(W\) function}, Adv. Comput. Math., 5 (1996), pp. 329-359. · Zbl 0863.65008 |
| [12] | R.J. Duffin, {\it Topology of series-parallel graphs}, J. Math. Anal. Appl., 10 (1965), pp. 303-318. · Zbl 0128.37002 |
| [13] | E.J. Farrell, {\it Chromatic roots — some observations and conjectures}, Discrete Math., 29 (1980), pp. 161-167. · Zbl 0443.05040 |
| [14] | R. Fernández and A. Procacci, {\it Regions without complex zeros for chromatic polynomials on graphs with bounded degree}, Combin. Probab. Comput., 17 (2008), pp. 225-238 · Zbl 1171.05017 |
| [15] | G. Grimmett, {\it The Random-Cluster Model}, Springer-Verlag, Berlin, 2006. · Zbl 1122.60087 |
| [16] | B. Jackson, {\it Zeros of chromatic and flow polynomials of graphs}, J. Geom., 76 (2003), pp. 95-109. · Zbl 1021.05033 |
| [17] | B. Jackson, A. Procacci, and A.D. Sokal, {\it Complex zero-free regions at large \(|q|\) for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights}, J. Combin. Theory Ser. B, 103 (2013), pp. 21-45. · Zbl 1257.05068 |
| [18] | B. Jackson and A.D. Sokal, {\it Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids}, J. Combin. Theory Ser. B, 99 (2009), pp. 869-903. · Zbl 1221.05144 |
| [19] | B. Jackson and A.D. Sokal, {\it Maxmaxflow and counting subgraphs}, Electron. J. Combin., 17 (2010), R99. · Zbl 1230.05175 |
| [20] | J. Oxley, {\it Graphs and series-parallel networks}, in Theory of Matroids, N. White, ed., Cambridge University Press, Cambridge, 1986, pp. 97-126. · Zbl 0587.05020 |
| [21] | J.G. Oxley, {\it Matroid Theory}, Oxford University Press, New York, 1992. · Zbl 0784.05002 |
| [22] | Q.I. Rahman and G. Schmeisser, {\it Analytic Theory of Polynomials}, Clarendon Press/Oxford University Press, Oxford, 2002. · Zbl 1072.30006 |
| [23] | R.C. Read and G.F. Royle, {\it Chromatic roots of families of graphs}, in Graph Theory, Combinatorics, and Applications, Vol. 2, Y. Alavi, G. Chartrand, O.R. Oellermann, and A.J. Schwenk, eds., Wiley, New York, 1991, pp. 1009-1029. · Zbl 0841.05034 |
| [24] | G. Royle and A.D. Sokal, {\it The Brown-Colbourn conjecture on zeros of reliability polynomials is false}, J. Combin. Theory Ser. B, 91 (2004), pp. 345-360. · Zbl 1052.05038 |
| [25] | G.F. Royle, {\it Recent results on chromatic and flow roots of graphs and matroids}, in Surveys in Combinatorics, 2009, S. Huczynska, J.D. Mitchell, and C.M. Roney-Dougal, eds., Cambridge University Press, Cambridge, 2009, pp. 289-327. · Zbl 1210.05062 |
| [26] | G.F. Royle and A.D. Sokal, {\it Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graph}, expanded version, preprint, arXiv.1307.1721, 2013. |
| [27] | J. Salas and A.D. Sokal, {\it Chromatic Roots of the Complete Bipartite Graphs}, manuscript, 2015. |
| [28] | R. Shrock and S.-H. Tsai, {\it Ground-state degeneracy of Potts antiferromagnets: Cases with noncompact \(W\) boundaries having multiple points at \(1/q=0\)}, J. Phys. A, 31 (1998), pp. 9641-9665. |
| [29] | R. Shrock and S.-H. Tsai, {\it Ground-state degeneracy of Potts antiferromagnets: Homeomorphic classes with noncompact \(W\) boundaries}, Phys. A, 265 (1999), pp. 186-223. |
| [30] | A.D. Sokal, {\it Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions}, Combin. Probab. Comput., 10 (2001), pp. 41-77. · Zbl 0999.82022 |
| [31] | A.D. Sokal, {\it Chromatic roots are dense in the whole complex plane}, Combin. Probab. Comput., 13 (2004), pp. 221-261. · Zbl 1100.05040 |
| [32] | A.D. Sokal, {\it The multivariate Tutte polynomial (alias Potts model) for graphs and matroids}, in Surveys in Combinatorics, 2005, B.S. Webb, ed., Cambridge University Press, Cambridge, 2005, pp. 173-226. · Zbl 1110.05020 |
| [33] | J.P. Spinrad, {\it Efficient Graph Representations}, AMS, Providence RI, 2003. · Zbl 1033.05001 |
| [34] | C. Thomassen, {\it The zero-free intervals for chromatic polynomials of graphs}, Combin. Probab. Comput., 6 (1997), pp. 497-506. · Zbl 0887.05020 |
| [35] | J. Valdes, R.E. Tarjan, and E.L. Lawler, {\it The recognition of series parallel digraphs}, SIAM J. Comput., 11 (1982), pp. 298-313. · Zbl 0478.68065 |
| [36] | D.G. Wagner, {\it Zeros of reliability polynomials and \(f\)-vectors of matroids}, Combin. Probab. Comput., 9 (2000), pp. 167-190. · Zbl 0994.05085 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
