Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-23T13:36:41.206Z Has data issue: false hasContentIssue false
  • English
  • Français

Bounds For The Real Zeros of Chromatic Polynomials

Published online by Cambridge University Press:  01 November 2008

F. M. DONG  and
K. M. KOH
F. M. DONG
Affiliation:
Mathematics and Mathematics Education, National Institute of Education, Nanyang Technological University, Singapore637616 (e-mail: [email protected])
K. M. KOH
Affiliation:
Department of Mathematics, National University of Singapore, Singapore117543
Get access Rights & Permissions [Opens in a new window]

Abstract

Sokal in 2001 proved that the complex zeros of the chromatic polynomial PG(q) of any graph G lie in the disc |q| < 7.963907Δ, where Δ is the maximum degree of G. This result answered a question posed by Brenti, Royle and Wagner in 1994 and hence proved a conjecture proposed by Biggs, Damerell and Sands in 1972. Borgs gave a short proof of Sokal's result. Fernández and Procacci recently improved Sokal's result to |q| < 6.91Δ. In this paper, we shall show that all real zeros of PG(q) are in the interval [0,5.664Δ). For the special case that Δ = 3, all real zeros of PG(q) are in the interval [0,4.765Δ).

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 6 , November 2008 , pp. 749 - 759
Copyright
Copyright © Cambridge University Press 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Biggs, N. L., Damerell, R. M. and Sands, D. A. (1972) Recursive families of graphs. J. Combin. Theory Ser. B 12 123–131.CrossRefGoogle Scholar
[2]Birkhoff, G. D. (1912) A determinantal formula for the number of ways of coloring a map. Ann. Math. 14 42–46.CrossRefGoogle Scholar
[3]Borgs, C. (2006) Absence of zeros for the chromatic polynomial on bounded degree graphs. Combin. Probab. Comput. 15 63–74.CrossRefGoogle Scholar
[4]Brenti, F., Royle, G. F. and Wagner, D. G. (1994) Location of zeros of chromatic and related polynomials of graphs. Canad. J. Math. 46 55–80.CrossRefGoogle Scholar
[5]Corless, R. M., Gonnet, G. H., Hare, D. E. G., Jeffrey, D. J. and Knuth, D. E. (1996) On the Lambert W function. Adv. Comput. Math. 5 329–359.CrossRefGoogle Scholar
[6]Dobrushin, R. L. (1996) Estimates of semi-invariants for the Ising model at low temperatures. In Topics in Statistical and Theoretical Physics, Vol. 177 of American Mathematical Society Translations, Ser. 2, pp. 59–81.Google Scholar
[7]Dobrushin, R. L. (1996) Perturbation methods of the theory of Gibbsian fields. In Lectures on Probability Theory and Statistics: Ecole d'Eté de Probabilités de Saint-Flour XXIV (Bernard, P., ed.) Vol. 1648 of Lecture Notes in Mathematics, Springer, Berlin, pp. 1–66.CrossRefGoogle Scholar
[8]Dong, F. M. and Koh, K. M. (2004) Two results on real zeros of chromatic polynomials. Combin. Probab. Comput. 13 809–813.Google Scholar
[9]Dong, F. M., Koh, K. M. and Teo, K. L. (2005) Chromatic Polynomials and Chromaticity of Graphs, World Scientific.Google Scholar
[10]Fernández, R. and Procacci, A. (2007) Cluster expansion for abstract polymer models: New bounds from an old approach. Comm. Math. Phys. 274 123–140.CrossRefGoogle Scholar
[11]Fernández, R. and Procacci, A. (2008) Regions without complex zeros for chromatic polynomials on graphs with bounded degree. Combin. Probab. Comput. 17 225–238.CrossRefGoogle Scholar
[12]Fortuin, C. M. and Kasteleyn, P. W. (1972) On the random-cluster model I: Introduction and relation to other models. Physica 57 536–564.CrossRefGoogle Scholar
[13]Jackson, B. (1993) A zero-free interval for chromatic polynomials of graphs. Combin. Probab. Comput. 2 325–336.Google Scholar
[14]Jackson, B. (2003) Zeros of chromatic and flow polynomials of graphs. J. Geom. 76 95–109. math.CO/0205047 at arXiv.org.CrossRefGoogle Scholar
[15]Kasteleyn, P. W. and Fortuin, C. M. (1969) Phase transitions in lattice systems with random local properties. J. Phys. Soc. Japan 26 (suppl.)11–14.Google Scholar
[16]Kotecký, R. and Preiss, D. (1986) Cluster expansion for abstract polymer models, Comm. Math. Phys. 103 491–498.CrossRefGoogle Scholar
[17]Salas, J. and Sokal, A. D. Chromatic roots of the complete bipartite graphs. In preparation; cited in [20].Google Scholar
[18]Scott, A. D. and Sokal, A. D. (2005) The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma. J. Statist. Phys. 118 1151–1261. cond-mat/0309352 at arXiv.org.CrossRefGoogle Scholar
[19]Sokal, A. D. (2001) Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions. Combin. Probab. Comput. 10 41–77. cond-mat/9904146 at arXiv.org.Google Scholar
[20]Sokal, A. D. (2005) The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. In Surveys in Combinatorics 2005 (Webb, B. S., ed.), Cambridge University Press, pp. 173–226. math.CO/0503607 at arXiv.org.Google Scholar