Combinatorial Optimization Reading Group- Rose McCarty

Title: 2-approximation of chromatic number on graph classes excluding a minor

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.