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

摘要

A class g of graphs is chi-bounded if there is a function f such that for every graph G is an element of g and every induced subgraph H of G, chi(H) <= f (omega(H)). In addition, we say that G is polynomially chi-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 chi(H) <= f (omega(H)) for all graphs with no vertex-minor isomorphic to the cycle graph C-n. To prove this, we show that if G is polynomially chi-bounded, then so is the closure of g under taking the 1-join operation. (C) 2019 Elsevier Inc. All rights reserved.