Classes of graphs with no long cycle as a vertex-minor are polynomially χ-bounded

Abstract

© 2019 Elsevier Inc.A class G of graphs is χ-bounded if there is a function f such that for every graph G∈G and every induced subgraph H of G, χ(H)⩽f(ω(H)). In addition, we say that G is polynomially χ-bounded if f can be taken as a polynomial function. We prove that for every integer n⩾3, there exists a polynomial f such that χ(G)⩽f(ω(G)) for all graphs with no vertex-minor isomorphic to the cycle graph Cn. To prove this, we show that if G is polynomially χ-bounded, then so is the closure of G under taking the 1-join operation