Tutte relations, TQFT, and planarity of cubic graphs

zbMATH Open1365.05137arXiv1512.07339MaRDI QIDQ2359552FDOQ2359552

Authors: Vyacheslav Krushkal, Ian Agol 

Publication date: 22 June 2017

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

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.

Full work available at URL: https://arxiv.org/abs/1512.07339

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

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)

Cited In (7)

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

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)