Remote Access Transactions of the American Mathematical Society
Green Open Access

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

David M. Jackson
Affiliation: Department of Combinatorics and Optimization, University of Waterloo, Ontario, Canada N2L 3G1

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

American Mathematical Society