Substitution and $χ$-Boundedness

A class $\mathcal{G}$ of graphs is said to be {\em $χ$-bounded} if there is a function $f:\mathbb{N} \rightarrow \mathbb{R}$ such that for all $G \in \mathcal{G}$ and all induced subgraphs $H$ of $G$, $χ(H) \leq f(ω(H))$. In this paper, we show that if $\mathcal{G}$ is a $χ$-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 $χ$-bounded by a polynomial (respectively: exponential) function, then the closure of $\mathcal{G}$ under substitution is also $χ$-bounded by some polynomial (respectively: exponential) function. In addition, we show that if $\mathcal{G}$ is a $χ$-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 $χ$-bounded, as is the closure of $\mathcal{G}$ under the operations of substitution and gluing along a clique together.

No reviews yet.

No comments yet.