Intersections of graphs and $χ$-boundedness
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916668394962944 |
|---|---|
| author | Chaniotis, Aristotelis Koerts, Hidde Spirkl, Sophie |
| author_facet | Chaniotis, Aristotelis Koerts, Hidde Spirkl, Sophie |
| contents | Given $k$ graphs $G_{1}, \ldots, 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}, \ldots , \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 \ldots \cap G_{k}\}$ the graph-intersection of $\mathcal{G}_{1}, \ldots , \mathcal{G}_{k}$. The main motivation for the work presented in this paper is to try to understand under which conditions graph-intersection preserves $χ$-boundedness. We consider the following two questions:
Which graph classes have the property that their graph-intersection with every $χ$-bounded class of graphs is $χ$-bounded? We call such a class intersectionwise $χ$-guarding. We prove that classes of graphs which admit a certain kind of decomposition are intersectionwise $χ$-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 $χ$-guarding, and we characterize the intersectionwise $χ$-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 $χ$-bounded? We call such a class intersectionwise self-$χ$-guarding. We study intersectionwise self-$χ$-guarding classes which are defined by a single forbidden induced subgraph, and we prove a result which allows us construct intersectionwise self-$χ$-guarding classes from known intersectionwise $χ$-guarding classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_00153 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Intersections of graphs and $χ$-boundedness Chaniotis, Aristotelis Koerts, Hidde Spirkl, Sophie Combinatorics Given $k$ graphs $G_{1}, \ldots, 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}, \ldots , \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 \ldots \cap G_{k}\}$ the graph-intersection of $\mathcal{G}_{1}, \ldots , \mathcal{G}_{k}$. The main motivation for the work presented in this paper is to try to understand under which conditions graph-intersection preserves $χ$-boundedness. We consider the following two questions: Which graph classes have the property that their graph-intersection with every $χ$-bounded class of graphs is $χ$-bounded? We call such a class intersectionwise $χ$-guarding. We prove that classes of graphs which admit a certain kind of decomposition are intersectionwise $χ$-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 $χ$-guarding, and we characterize the intersectionwise $χ$-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 $χ$-bounded? We call such a class intersectionwise self-$χ$-guarding. We study intersectionwise self-$χ$-guarding classes which are defined by a single forbidden induced subgraph, and we prove a result which allows us construct intersectionwise self-$χ$-guarding classes from known intersectionwise $χ$-guarding classes. |
| title | Intersections of graphs and $χ$-boundedness |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2504.00153 |