Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-17T06:15:30.259Z 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: [email protected])
CARSTEN THOMASSEN
Affiliation:
Department of Applied Mathematics and Computer Science, Technical University of Denmark, DK-2800 Lyngby, Denmark (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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 hypergraphs 05C83: Graph minors
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 6 , November 2018 , pp. 988 - 998
Copyright
Copyright © Cambridge University Press 2018 

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

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