Tutte proved that if G _(pt) is a planar triangulation and P(G _(pt), q) is its chromatic polynomial, then |P(G _(pt), τ+ 1)| ≤ (τ-1) ~(n-5), where τ=(1+√5)/2 and n is the number of vertices in G _(pt). Here we study the ratio r(G _(pt)) = |P(G _(pt), τ+1)|/(τ-1) ~(n-5) for a variety of planar triangulations. We construct infinite recursive families of planar triangulations G _(pt, m) depending on a parameter m linearly related to n and show that if P(G _(pt, m), q) only involves a single power of a polynomial, then r(G _(pt, m)) approaches zero exponentially fast as n→∞. We also construct infinite recursive families for which P(G _(pt, m), q) is a sum of powers of certain functions and show that for these, r(G _(pt, m)) may approach a finite nonzero constant as n→∞. The connection between the Tutte upper bound and the observed chromatic zero(s) near to τ+ 1 is investigated. We report the first known graph for which the zero(s) closest to τ+ 1 is not real, but instead is a complex-conjugate pair. Finally, we discuss connections with the nonzero ground-state entropy of the Potts antiferromagnet on these families of graphs.
展开▼
