Title: 2-approximation of chromatic number on graph classes excluding a minor
|Affiliation:||University of Waterloo|
Abstract: In this talk we will see a 2-approximation of the chromatic number of graphs excluding a fixed minor. The main step is an efficient algorithm to find a partition of the vertex set into two parts of bounded tree-width. This talk is based on work of Demaine, Hajiaghayi, and Kawarabayashi, and of Baker.
200 University Avenue West
Waterloo, ON N2L 3G1