Rainbow spanning structures in graph and hypergraph systems

Abstract

We study the following rainbow version of subgraph containment problems in a family of (hyper)graphs, which generalizes the classical subgraph containment problems in a single host graph. For a collection $\mathit {\mathbf {G}}=\{G_1, G_2,\ldots , G_{m}\}$ of not necessarily distinct k-graphs on the same vertex set $[n]$ , a (sub)graph H on $[n]$ is rainbow if there exists an injection $\varphi : E(H)\rightarrow [m]$ , such that $e\in E(G_{\varphi (e)})$ for each $e\in E(H)$ . Note that if $|E(H)|=m$ , then $\varphi $ is a bijection, and thus H contains exactly one edge from each $G_i$ .

Keywords

• 05C35
• 05C65