Intersections of graphs and $\ddot{I}‡$-boundedness

Abstract

Given $k$ graphs $G_1,\dots ,G_k$, their intersection is the graph $({\cap }_{i\in [k]}V(G_i),{\cap }_{i\in [k]}E(G_i))$. Given $k$ graph classes ${\mathcal{G}}_1,\dots ,{\mathcal{G}}_k$, we call the class $\{G:\forall i\in [k],\exists G_i\in {\mathcal{G}}_i\text{ such that }G=G_1\cap \dots \cap G_k\}$ the graph-intersection of ${\mathcal{G}}_1,\dots ,{\mathcal{G}}_k$. The main motivation for the work presented in this paper is to try to understand under which conditions graph-intersection preserves $\ddot{I}‡$-boundedness. We consider the following two questions: Which graph classes have the property that their graph-intersection with every $\ddot{I}‡$-bounded class of graphs is $\ddot{I}‡$-bounded? We call such a class intersectionwise $\ddot{I}‡$-guarding. We prove that classes of graphs which admit a certain kind of decomposition are intersectionwise $\ddot{I}‡$-guarding. We provide necessary conditions that a finite set of graphs $\mathcal{H}$ should satisfy if the class of $\mathcal{H}$-free graphs is intersectionwise $\ddot{I}‡$-guarding, and we characterize the intersectionwise $\ddot{I}‡$-guarding classes which are defined by a single forbidden induced subgraph. Which graph classes have the property that, for every positive integer $k$, their $k$-fold graph-intersection is $\ddot{I}‡$-bounded? We call such a class intersectionwise self-$\ddot{I}‡$-guarding. We study intersectionwise self-$\ddot{I}‡$-guarding classes which are defined by a single forbidden induced subgraph, and we prove a result which allows us construct intersectionwise self-$\ddot{I}‡$-guarding classes from known intersectionwise $\ddot{I}‡$-guarding classes.