On-Line Graph Coloring

ACO Student Seminar
Wednesday, February 17, 2010 - 13:30
1 hour (actually 50 minutes)
ISyE Executive Classroom
School of Mathematics, Georgia Tech
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.