<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 1" %>
Planar Triangulations with Real Chromatic Roots Arbitrarily Close to 4
Gordon Royle
School of Computer Science & Software Engineering, University of Western Australia, 35 Stirling Highway, Nedlands, WA 6009, Australia
gordon@csse.uwa.edu.au
Annals of Combinatorics 12 (2) p.195-210 June, 2008
AMS Subject Classification: 05C99; 05C15
Abstract:
We exhibit infinite families of planar triangulations with real chromatic roots arbitrarily close to 4, thus resolving a long-standing conjecture in the affirmative.
Keywords: chromatic polynomial, chromatic root, planar triangulation, cylindrical triangular lattice, Birkhoff-Lewis conjecture

References:

1. S. Beraha and J. Kahane, Is the four-color conjecture almost false?, J. Combin. Theory Ser. B 27 (1) (1979) 1-–12.

2. S. Beraha, J. Kahane, and N.J. Weiss, Limits of zeros of recursively dened families of polynomials, In: Studies in Foundations and Combinatorics, Adv. in Math. Suppl. Stud., Vol. 1., Academic Press, New York, (1978) pp. 213–-232.

3. G. Berman and W.T. Tutte, The golden root of a chromatic polynomial, J. Combin. Theory 6 (1969) 301-–302.

4. D.A. Bini and G. Fiorentino, Design, analysis, and implementation of a multiprecision polynomial rootnder, Numer. Algorithms 23 (2-3) (2000) 127-–173.

5. G.D. Birkhoff, A determinant formula for the number of ways of coloring a map, Ann. of Math. (2) 14 (1-4) (1912/13) 42-–46.

6. G.D. Birkhoff and D.C. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60 (1946) 355-–451.

7. S.-C. Chang, J.L. Jacobsen, J. Salas, and R. Shrock, Exact Potts model partition functions for strips of the triangular lattice, J. Statist. Phys. 114 (3-4) (2004) 763–-823.

8. S.-C. Chang and R. Shrock, Transfer matrices for the zero-temperature Potts antiferromagnet on cyclic and M¨obius lattice strips, Phys. A 346 (2005) 400-–450.

9. G. Haggard and T.R. Mathies, The computation of chromatic polynomials, Discrete Math. 199 (1-3) (1999) 227–-231.

10. D.W. Hall, J.W. Siry, and B.R. Vanderslice, The chromatic polynomial of the truncated icosahedron, Proc. Amer. Math. Soc. 16 (1965) 620–-628.

11. B. Jackson, Zeros of chromatic and ow polynomials of graphs, J. Geom. 76 (1-2) (2003) 95-–109.

12. J.L. Jacobsen, J. Salas, and A.D. Sokal, Transfer matrices and partition-function zeros for antiferromagnetic Potts models. III. Triangular-lattice chromatic polynomial, J. Statist. Phys. 112 (5-6) (2003) 921–-1017.

13. M. Rocek, R. Shrock, and S.-H. Tsai, Chromatic polynomials for families of strip graphs and their asymptotic limits, Phys. A 252 (3-4) (1998) 505-–546.

14. M. Rocek, R. Shrock, and S.-H. Tsai, Chromatic polynomials for J(ÕH)I strip graphs and their asymptotic limits, Phys. A 259 (3-4) (1998) 367-–387.

15. J. Salas and A.D. Sokal, Transfer matrices and partition-function zeros for antiferromagnetic Potts models. I. general theory and square-lattice chromatic polynomial, J. Statist. Phys. 104 (3-4) (2001) 609–-699.

16. R. Shrock, Chromatic polynomials and their zeros and asymptotic limits for families of graphs, Discrete Math. 231 (1-3) (2001) 421-–446.

17. A. Sokal, Chromatic polynomials, Potts models and all that, Phys. A 279 (2000) 324-–332.

18. A.D. Sokal, Chromatic roots are dense in the whole complex plane, Combin. Probab. Comput. 13 (2) (2004) 221-–261.

19. T. Tantau, PGF and TikZ: Graphic systems for TEX, Version 1.00, 2005, http://sourceforge.net/projects/pgf.