Hostname: page-component-74656f9884-g96k6 Total loading time: 0 Render date: 2026-11-10T04:09:13.316Z 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: fengming.dong@nie.edu.sg)
K. M. KOH
Affiliation:
Department of Mathematics, National University of Singapore, Singapore117543
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.

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Δ).

Information

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

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