On a rainbow version of Dirac's theorem - Joos, Felix; Kim, Jaehoon (Arxiv, 2019)
For a collection $G=\{G_1,…, G_s\}$ of not necessarily distinct graphs on the same vertex set $V$, a graph $H$ with vertices in $V$ is a $G$-transversal if there exists a bijection $φ:E(H)→ [s]$ such that $e\in E(G_{φ(e)})$ for all $e\in E(H)$. We prove that for $|V|=s≥ 3$ and $δ(G_i)≥ s/2$ for each $i\in [s]$, there exists a $G$-transversal that is a Hamilton cycle. This confirms a conjecture of Aharoni. We also prove an analogous result for perfect matchings.
Identifizierung der Ressource nach: 15 Apr 2020
Gesehen am 27.07.2022