Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

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
Published electronically: August 18, 2009
MathSciNet review: 2550161
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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


References [Enhancements On Off] (What's this?)


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/S0002-9947-09-04836-3
PII: S 0002-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