Chi-boundedness of graph classes excluding wheel vertex-minors
Speaker:
Sang-il Oum, KAIST
Date and Time:
Thursday, October 12, 2017 - 1:30pm to 1:55pm
Location:
Fields Institute, Room 230
Abstract:
A class of graphs is χ-bounded if there exists a function f:N→N such that for every graph G in the class and an induced subgraph H of G, if H has no clique of size q+1, then the chromatic number of H is less than or equal to f(q). We denote by Wn the wheel graph on n+1 vertices. We show that the class of graphs having no vertex-minor isomorphic to Wn is χ-bounded. This generalizes several previous results; χ-boundedness for circle graphs, for graphs having no W5 vertex-minors, and for graphs having no fan vertex-minors. This is a joint work with Hoijn Choi, O-joung Kwon, and Paul Wollan.