====== Michael Gillen (Binghamton) ======

====== Colorings and Orientations of Graphs ======

===== Abstract for the Combinatorics Seminar 2011 May 10 =====

I will use algebraic techniques to put a bound on the chromatic number of a directed graph as a function of the outdegrees of the vertices. I will also deduce a lower bound on the maximum cardinality of an independent set of vertices. Finally, if time permits, I will demonstrate k-choosability of bipartite graphs for suitable k.

This talk is based on the paper "Colorings and Orientations of Graphs" (Combinatorica, 1989) by Alon and Tarsi.


----