Transversal factors and spanning trees

Abstract

Given a collection of graphs $\mathbf{G}=(G_1,\dots ,G_m)$ with the same vertex set, an $m$-edge graph $H\subset {\cup }_{i\in [m]}{G}_i$ is a transversal if there is a bijection $\varphi :E(H)\to [m]$ such that $e\in E(G_{\varphi (e)})$ for each $e\in E(H)$. We give asymptotically-tight minimum degree conditions for a graph collection on an $n$-vertex set to have a transversal which is a copy of a graph $H$, when $H$ is an $n$-vertex graph which is an $F$-factor or a tree with maximum degree $o(n/\log n)$.

arXiv comment21 pages