Monday, January 6th, 2014 | 4pm-5pm | Burnside 1205 |

E'cole Normale Supe'rieure de Lyon

Complements of chi-bounded graphs

Gyárfás introduced the notion of chi-bounded classes of graphs and we wish to determine which classes have this property. A class of graphs is chi-bounded if the chromatic number of each graph is bounded by a function of the clique number of that graph and in addition, this class is closed under taking induced subgraphs. We wish to determine for which function f are complements of graphs in any class chi-bounded by f also chi-bounded (by some other function g). We improve previous best known conditions on f. We also improve the best known function g binding the complement for some functions f. This is joint work with András Gyárfás, Raphael Machado, András Sebo, Stéphan Thomassé and Nicolas Trotignon.