Chromatic Polynomials of Planar Triangulations, the Tutte Upper Bound, and Chromatic Zeros

Details Chromatic Polynomials of Planar Triangulations, the Tutte Upper Bound, and Chromatic Zeros Chromatic Polynomials of Planar Triangulations, the Tutte Upper Bound, and Chromatic Zeros

2011-10-26

arxiv.org/abs/1110.5883v1

J. Phys. A: Math. Theor. 45, 055212 (2012)

Physics

Mathematical Physics

Scientific paper

10.1088/1751-811345/5/055212

Tutte proved that if $G_{pt}$ is a planar triangulation and $P(G_{pt},q)$ is its chromatic polynomial, then $|P(G_{pt},\tau+1)| \le (\tau-1)^{n-5}$, where $\tau=(1+\sqrt{5} \,)/2$ and $n$ is the number of vertices in $G_{pt}$. Here we study the ratio $r(G_{pt})=|P(G_{pt},\tau+1)|/(\tau-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 \to \infty$. 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 \to \infty$. The connection between the Tutte upper bound and the observed chromatic zero(s) near to $\tau+1$ is investigated. We report the first known graph for which the zero(s) closest to $\tau+1$ is not real, but instead is a complex-conjugate pair. Finally, we discuss connections with nonzero ground-state entropy of the Potts antiferromagnet on these families of graphs.

Affiliated with

Also associated with

No associations

Rating

Chromatic Polynomials of Planar Triangulations, the Tutte Upper Bound, and Chromatic Zeros does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Chromatic Polynomials of Planar Triangulations, the Tutte Upper Bound, and Chromatic Zeros, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Chromatic Polynomials of Planar Triangulations, the Tutte Upper Bound, and Chromatic Zeros will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-718022