Chi-boundedness of graph classes excluding wheel vertex-minors

Abstract

A class of graphs is X-bounded if there exists a function f : N -> Nsuch 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 W-n the wheel graph on n +1 vertices. We show that the class of graphs having no vertex-minor isomorphic to W-n is chi-bounded. This generalizes several previous results; chi-boundedness for circle graphs, for graphs having no W-5 vertex-minors, and for graphs having no fan vertex-minors. (C) 2018 Elsevier Inc. All rights reserved.