Combinatorial Optimization Reading Group- Sharat Imbrahimpur

Title: Coloring 3-colorable graphs with o(n^1/5) colors

Abstract: This is the second part of the seminar on recent results obtained by Kawarabayashi and Thorup for coloring 3-colorable graphs with o(n^1/5) colors. In the first part, Tom presented combinatorial techniques used in this paper which work well when the minimum degree in the graph is large. In this talk, I will present semidefinite programming based techniques which work well when the maximum degree is small.