Hopf algebras and polynomial graph invariants

Abstract

We begin with a brief introduction to the chromatic and Tutte polynomial of graphs. We then give an introduction to Hopf algebras. In combinatorics, Hopf algebras arise since many combinatorial objects have associated with them operations of union (leading to multiplicative structure) and decomposition (leading to a comultiplicative structure). We then discuss some classic results of Tutte on V and W functions andTutte polynomials. We show that the chromatic polynomial is the unique morphism in the category of Hopf algebras from a Hopf algebra of graphs to a Hopf algebra of polynomials, which is a result of Foissy. We then present a Hopf algebraic method of Schmitt for Whitney systems, demonstrating that the chromatic polynomial of a graph G can be determined by examining only the doubly connected subgraphs of G, which is a result of Whitney. The last chapter is on the reconstruction conjecture of Ulam and Kelly. Here we show that certain counting argument used by Kocay and Tutte are essentially identical to a counting argument used by Schmitt in his Hopf algebra methods for the chromatic polynomial.