MASTERS EXAM TALK

"Complexes of t-colorable graphs"

Daniel Wells
University of Kentucky

Wednesday, April 19, 2006
4:00 pm, 845 Patterson Office Tower

Abstract:

We say a graph is t-colorable if one can assign one of t colors to each vertex of the graph such that no adjacent vertices have the same color. Since any subgraph of a t-colorable graph is t-colorable, the set of all t-colorable graphs on a fixed vertex set can be considered an abstract simplicial complex with the t-colorable graphs as faces.

In their 2003 paper "Complexes of t-colorable graphs", Svante Linusson and John Shareshian apply the techniques of discrete Morse theory to the complex of t-colorable graphs on the fixed vertex set [n] to determine the homotopy type for t leq 2 and leq n-3. We will begin by giving a brief introduction to the combinatorial description (due to M. K. Chari) of Robin Forman's discrete Morse theory. We will then present the proof of Linusson and Shareshian's result for 2-colorable (bipartite) graphs and indicate how this same strategy can be applied to obtain the remaining results.