Substitution and $\chi$-Boundedness

Abstract

A class $\mathcal{G}$ of graphs is said to be {\em $\chi$-bounded} if there is a function $f:\mathbb{N}\to \mathbb{R}$ such that for all $G\in \mathcal{G}$ and all induced subgraphs $H$ of $G$, $\chi (H)\le f(\omega (H))$. In this paper, we show that if $\mathcal{G}$ is a $\chi$-bounded class, then so is the closure of $\mathcal{G}$ under any one of the following three operations: substitution, gluing along a clique, and gluing along a bounded number of vertices. Furthermore, if $\mathcal{G}$ is $\chi$-bounded by a polynomial (respectively: exponential) function, then the closure of $\mathcal{G}$ under substitution is also $\chi$-bounded by some polynomial (respectively: exponential) function. In addition, we show that if $\mathcal{G}$ is a $\chi$-bounded class, then the closure of $\mathcal{G}$ under the operations of gluing along a clique and gluing along a bounded number of vertices together is also $\chi$-bounded, as is the closure of $\mathcal{G}$ under the operations of substitution and gluing along a clique together.

Cited by in corpus (7)

• $\chi$-bounds, operations and chords
• Classes of graphs with no long cycle as a vertex-minor are polynomially $\chi$-bounded
• Coloring of ($P_5$, $4$-wheel)-free graphs
• Isolating highly connected induced subgraphs
• Graphs of bounded cliquewidth are polynomially $\chi$-bounded
• Reuniting $\chi$-boundedness with polynomial $\chi$-boundedness
• Square-free graphs with no six-vertex induced path