Tutte relations, TQFT, and planarity of cubic graphs

MaRDI QIDQ2359552zbMATH OpenFDO

Authors Vyacheslav Krushkal, Ian Agol

Publication date 22 June 2017

Published in Illinois Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.07339, https://projecteuclid.org/euclid.ijm/1498032033

zbMATH Keywords

chromatic polynomial of planar triangulations

Mathematics Subject Classification ID

Graph polynomials (05C31) Planar graphs; geometric and topological aspects of graph theory (05C10) Topological quantum field theories (aspects of differential topology) (57R56) Relations of low-dimensional topology with graph theory (57M15)

Abstract: It has been known since the work of Tutte that the value of the chromatic polynomial of planar triangulations at $(3+sqrt5)/2$ has a number of remarkable properties. We investigate to what extent Tutte's relations characterize planar graphs. A version of the Tutte linear relation for the flow polynomial at $(3-sqrt5)/2$ is shown to give a planarity criterion for $3$-connected cubic graphs. A conjecture is formulated that the golden identity for the flow polynomial characterizes planarity of cubic graphs as well. In addition, Tutte's upper bound on the chromatic polynomial of planar triangulations at $(3+sqrt5)/2$ is generalized to other Beraha numbers, and an exponential lower bound is given for the value at $(3-sqrt5)/2$. The proofs of these results rely on the structure of the Temperley-Lieb algebra and more generally on methods of topological quantum field theory.

Recommendations

• Tutte chromatic identities from the Temperley-Lieb algebra
• Structure of the flow and Yamada polynomials of cubic graphs
• scientific article; zbMATH DE number 4065016
• Chromatic polynomials of planar triangulations, the Tutte upper bound and chromatic zeros
• On the evaluation at (3,3) of the Tutte polynomial of a graph

Cited in

(6)

• Tutte chromatic identities from the Temperley-Lieb algebra
• Maximum number of colourings: 4-chromatic graphs
• Structure of the flow and Yamada polynomials of cubic graphs
• Planar diagrams for local invariants of graphs in surfaces
• Topological quantum field theory and polynomial identities for graphs on the torus
• Density of roots of the Yamada polynomial of spatial graphs

This page was built for publication: Tutte relations, TQFT, and planarity of cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2359552)