On Tutte's chromatic invariant

Authors:
Sabin Cautis and David M. Jackson

Journal:
Trans. Amer. Math. Soc. **362** (2010), 491-507

MSC (2000):
Primary 05C15

DOI:
https://doi.org/10.1090/S0002-9947-09-04836-3

Published electronically:
August 18, 2009

MathSciNet review:
2550161

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Consider a simple connected graph embedded in the plane together with a contractible circuit . For a partition of the vertex set of we denote by the number of ways of assigning one of given colours to each vertex of so that vertices in the same block of have the same colour. Tutte showed that this polynomial may be expressed uniquely as a linear combination of over all planar partitions of , with scalars that are independent of . We show that the (chromatic) invariants have a natural algebraic setting in terms of the orthogonal projection from the partition algebra to the Temperley-Lieb subalgebra . We define the genus of a partition and give an extension of the invariants to arbitrary genus . Finally, we summarise the rôle of the genus 0 invariants in the algebraic approach of Birkhoff and Lewis to the Four Colour Theorem.

**[AH1]**K. Appel and W. Haken,*Every planar map is four colorable. I. Discharging*, Illinois J. Math.**21**(1977), no. 3, 429–490. MR**0543792****[AHK]**K. Appel, W. Haken, and J. Koch,*Every planar map is four colorable. II. Reducibility*, Illinois J. Math.**21**(1977), no. 3, 491–567. MR**0543793****[BL]**G. D. Birkhoff and D. C. Lewis,*Chromatic polynomials*, Trans. Amer. Math. Soc.**60**(1946), 355–451. MR**0018401**, https://doi.org/10.1090/S0002-9947-1946-0018401-4**[CJ]**S. Cautis and D. M. Jackson,*The matrix of chromatic joins and the Temperley-Lieb algebra*, J. Combin. Theory Ser. B**89**(2003), no. 1, 109–155. MR**1999738**, https://doi.org/10.1016/S0095-8956(03)00071-6**[K]**Louis H. Kauffman,*Statistical mechanics and the Jones polynomial*, Braids (Santa Cruz, CA, 1986) Contemp. Math., vol. 78, Amer. Math. Soc., Providence, RI, 1988, pp. 263–297. MR**975085**, https://doi.org/10.1090/conm/078/975085**[KT]**L. Kauffman and R. Thomas,*Temperley-Lieb algebras and the Four Colour Theorem*. Available at*http://math.uic.edu/kauffman/TLFCT.pdf*.**[HR]**Tom Halverson and Arun Ram,*Partition algebras*, European J. Combin.**26**(2005), no. 6, 869–921. MR**2143201**, https://doi.org/10.1016/j.ejc.2004.06.005**[J]**V. F. R. Jones, Planar Algebras, I.*http://xxx.lanl.gov/abs/math/9909027*.**[M]**Paul Martin,*Potts models and related problems in statistical mechanics*, Series on Advances in Statistical Mechanics, vol. 5, World Scientific Publishing Co., Inc., Teaneck, NJ, 1991. MR**1103994****[RSST]**Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas,*The four-colour theorem*, J. Combin. Theory Ser. B**70**(1997), no. 1, 2–44. MR**1441258**, https://doi.org/10.1006/jctb.1997.1750**[S]**Richard P. Stanley,*Enumerative combinatorics. Vol. 1*, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997. With a foreword by Gian-Carlo Rota; Corrected reprint of the 1986 original. MR**1442260****[To]**Private communication*per*J. Geelen, December 2004.**[T1]**W. T. Tutte,*On the Birkhoff-Lewis equations*, Discrete Math.**92**(1991), no. 1-3, 417–425. MR**1140602**, https://doi.org/10.1016/0012-365X(91)90296-E**[T2]**W. T. Tutte,*The matrix of chromatic joins*, J. Combin. Theory Ser. B**57**(1993), no. 2, 269–288. MR**1207492**, https://doi.org/10.1006/jctb.1993.1021

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (2000):
05C15

Retrieve articles in all journals with MSC (2000): 05C15

Additional Information

**Sabin Cautis**

Affiliation:
Department of Mathematics, Rice University, Houston, Texas 77251

Email:
scautis@math.harvard.edu

**David M. Jackson**

Affiliation:
Department of Combinatorics and Optimization, University of Waterloo, Ontario, Canada N2L 3G1

Email:
dmjackson@math.uwaterloo.ca

DOI:
https://doi.org/10.1090/S0002-9947-09-04836-3

Keywords:
Chromatic invariant,
non-crossing partitions,
Temperley-Lieb algebra,
partition algebra,
Birkhoff-Lewis equations

Received by editor(s):
February 1, 2006

Received by editor(s) in revised form:
July 11, 2007, and May 9, 2008

Published electronically:
August 18, 2009

Article copyright:
© Copyright 2009
American Mathematical Society