Combinatorial Optimization Reading Group- Tom Kelly

Friday, February 8, 2019 1:00 pm - 1:00 pm EST (GMT -05:00)

Title:‘Coloring 3-colorable graphs with o(n^1⁄5) colors’ by Kawarabayashi and Thorup

Speaker: Tom Kelly
Affiliation: University of Waterloo
Room: MC 5479

Abstract: Much attention has been devoted to nding polynomial time algorithms for coloring three-
colorable graphs with the fewest possible colors. Kawarabayashi and Thorup recently found
such an algorithm using o(n1=5) colors, where n is the number of vertices. Their approach uses
a new combinatorial recursion combined with semi-denite programming. In this talk, I will
present the combinatorial aspects of their result.