On Tutte's chromatic invariant
Authors:
Sabin Cautis and David M. Jackson
Journal:
Trans. Amer. Math. Soc. 362 (2010), 491507
MSC (2000):
Primary 05C15
Published electronically:
August 18, 2009
MathSciNet review:
2550161
Fulltext 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 TemperleyLieb 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
(58 #27598a)
 [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
(58 #27598b)
 [BL]
G.
D. Birkhoff and D.
C. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60 (1946), 355–451. MR 0018401
(8,284f), http://dx.doi.org/10.1090/S00029947194600184014
 [CJ]
S.
Cautis and D.
M. Jackson, The matrix of chromatic joins and the TemperleyLieb
algebra, J. Combin. Theory Ser. B 89 (2003),
no. 1, 109–155. MR 1999738
(2004g:05046), http://dx.doi.org/10.1016/S00958956(03)000716
 [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
(89j:57002), http://dx.doi.org/10.1090/conm/078/975085
 [KT]
L. Kauffman and R. Thomas, TemperleyLieb 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
(2006g:05228), http://dx.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
(92m:82030)
 [RSST]
Neil
Robertson, Daniel
Sanders, Paul
Seymour, and Robin
Thomas, The fourcolour theorem, J. Combin. Theory Ser. B
70 (1997), no. 1, 2–44. MR 1441258
(98c:05065), http://dx.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 GianCarlo Rota; Corrected reprint of
the 1986 original. MR 1442260
(98a:05001)
 [To]
Private communication per J. Geelen, December 2004.
 [T1]
W.
T. Tutte, On the BirkhoffLewis equations, Discrete Math.
92 (1991), no. 13, 417–425. MR 1140602
(92k:05052), http://dx.doi.org/10.1016/0012365X(91)90296E
 [T2]
W.
T. Tutte, The matrix of chromatic joins, J. Combin. Theory
Ser. B 57 (1993), no. 2, 269–288. MR 1207492
(94a:05144), http://dx.doi.org/10.1006/jctb.1993.1021
 [AH1]
 K. Appel and W. Haken, Every planar map is four colorable. Part I. Discharging, Illinois J. Math. 21 (1977), 429490. MR 0543792 (58:27598a)
 [AHK]
 K. Appel, W. Haken, and J. Koch, Every planar map is four colorable. Part II. Reducibility, Illinois J. Math. 21 (1977), 491567. MR 0543793 (58:27598b)
 [BL]
 G. D. Birkhoff and D. C. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60 (1946), 355451. MR 0018401 (8:284f)
 [CJ]
 S. Cautis and D. M. Jackson, The matrix of chromatic joins and the TemperleyLieb algebra, J. Combin. Theory (Ser. B) 89 (2003), 109155. MR 1999738 (2004g:05046)
 [K]
 L. Kauffman, Statistical mechanics and the Jones polynomial, Contemp. Math. 78 (1988), 263297. MR 975085 (89j:57002)
 [KT]
 L. Kauffman and R. Thomas, TemperleyLieb algebras and the Four Colour Theorem. Available at http://math.uic.edu/kauffman/TLFCT.pdf.
 [HR]
 T. Halverson and A. Ram, Partition algebras, European J. Combinatorics 26 (2005), 869921. MR 2143201 (2006g:05228)
 [J]
 V. F. R. Jones, Planar Algebras, I. http://xxx.lanl.gov/abs/math/9909027.
 [M]
 P. Martin, Potts Models and Related Problems in Statistical Mechanics, World Scientific, 1991. MR 1103994 (92m:82030)
 [RSST]
 N. Robertson, D. P. Sanders, P. D. Seymour and R. Thomas, The four colour theorem, J. Combin. Theory (Ser. B) 70 (1997), 244. MR 1441258 (98c:05065)
 [S]
 R. P. Stanley, Enumerative Combinatorics, vols. 1, 2, Cambridge Studies in Advanced Mathematics 62, Cambridge University Press, 1997, 1999. MR 1442260 (98a:05001)
 [To]
 Private communication per J. Geelen, December 2004.
 [T1]
 W. T. Tutte, On the BirkhoffLewis equations, Discrete Math. 92 (1991), 417425. MR 1140602 (92k:05052)
 [T2]
 W. T. Tutte, The matrix of chromatic joins, J. Combin. Theory (Ser. B) 57 (1993), 269288. MR 1207492 (94a:05144)
Similar Articles
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:
http://dx.doi.org/10.1090/S0002994709048363
PII:
S 00029947(09)048363
Keywords:
Chromatic invariant,
noncrossing partitions,
TemperleyLieb algebra,
partition algebra,
BirkhoffLewis 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
