On Tutte’s chromatic invariant

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.