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

Abstract

A class $\mathcal{G}$ of graphs is $\chi$-bounded if there is a function $f$ such that for every graph $G\in \mathcal{G}$ and every induced subgraph $H$ of $G$, $\chi (H)\le f(\omega (H))$. In addition, we say that $\mathcal{G}$ is polynomially $\chi$-bounded if $f$ can be taken as a polynomial function. We prove that for every integer $n\ge 3$, there exists a polynomial $f$ such that $\chi (G)\le f(\omega (G))$ for all graphs with no vertex-minor isomorphic to the cycle graph $C_n$. To prove this, we show that if $\mathcal{G}$ is polynomially $\chi$-bounded, then so is the closure of $\mathcal{G}$ under taking the $1$-join operation.

15 pages, 2 figures