Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-15T14:35:13.020Z Has data issue: false hasContentIssue false
  • English
  • Français

Density of Chromatic Roots in Minor-Closed Graph Families

Part of:Graph theory

Published online by Cambridge University Press:  22 April 2018

THOMAS J. PERRETT and
CARSTEN THOMASSEN
THOMAS J. PERRETT
Affiliation:
Department of Applied Mathematics and Computer Science, Technical University of Denmark, DK-2800 Lyngby, Denmark (e-mail: perrettt02@hotmail.com)
CARSTEN THOMASSEN
Affiliation:
Department of Applied Mathematics and Computer Science, Technical University of Denmark, DK-2800 Lyngby, Denmark (e-mail: perrettt02@hotmail.com)
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.

We prove that the roots of the chromatic polynomials of planar graphs are dense in the interval between 32/27 and 4, except possibly in a small interval around τ + 2 where τ is the golden ratio. This interval arises due to a classical result of Tutte, which states that the chromatic polynomial of every planar graph takes a positive value at τ + 2. Our results lead us to conjecture that τ + 2 is the only such number less than 4.

MSC classification

Primary:05C31: Graph polynomials
Secondary:05C15: Coloring of graphs and hypergraphs05C83: Graph minors

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 6 , November 2018, pp. 988 - 998
Copyright
Copyright © Cambridge University Press 2018 

Footnotes

†

Research supported by ERC Advanced Grant GRACOL, project number 320812.

References

[1] Birkhoff, G. D. (1912) A determinant formula for the number of ways of coloring a map. Ann. of Math. 12 42–46.Google Scholar
[2] Birkhoff, G. D. and Lewis, D. C. (1946) Chromatic polynomials. Trans. Amer. Math. Soc. 60 355–451.Google Scholar
[3] Jackson, B. (1993) A zero-free interval for chromatic polynomials of graphs. Combin. Probab. Comput. 2 325–336.Google Scholar
[4] Perrett, T. J. (2016) Roots of the chromatic polynomial. PhD thesis, Technical University of Denmark.Google Scholar
[5] Royle, G. (2008) Planar triangulations with real chromatic roots arbitrarily close to four. Ann. Combin. 12 195–210.Google Scholar
[6] Salas, J. and Sokal, A. D. (2001) Transfer matrices and partition-function zeros for antiferromagnetic Potts models I: General theory and square-lattice chromatic polynomial. J. Statist. Phys. 104 609–699.Google Scholar
[7] Sokal, A. D. (2004) Chromatic roots are dense in the whole complex plane. Combin. Probab. Comput. 13 221–261.Google Scholar
[8] Thomassen, C. (1997) The zero-free intervals for chromatic polynomials of graphs. Combin. Probab. Comput. 6 497–506.Google Scholar
[9] Tutte, W. T. (1970) The golden ratio in the theory of chromatic polynomials. Ann. New York Acad. Sci. 175 391–402.Google Scholar
[10] Wagner, K. (1937) Über eine Eigenschaft der ebenen Komplexe. Math. Ann. 114 570–590.Google Scholar