On-Line Graph Coloring

ACO Student Seminar
Wednesday, February 17, 2010 - 1:30pm for 1 hour (actually 50 minutes)
ISyE Executive Classroom
William T. Trotter – School of Mathematics, Georgia Tech
Sarah Fletcher
On-line graph coloring has a rich history, with a very large number of elegant results together with a near equal number of unsolved problems. In this talk, we will briefly survey some of the classic results including: performance on k-colorable graphs and \chi-bounded classes. We will conclude with a sketch of some recent and on-going work, focusing on the analysis of First Fit on particular classes of graphs.