Back to Search Start Over

On a rainbow version of Dirac's theorem

Authors :
Joos, Felix
Kim, Jaehoon
Publication Year :
2019

Abstract

For a collection $\mathbf{G}=\{G_1,\dots, G_s\}$ of not necessarily distinct graphs on the same vertex set $V$, a graph $H$ with vertices in $V$ is a $\mathbf{G}$-transversal if there exists a bijection $\phi:E(H)\rightarrow [s]$ such that $e\in E(G_{\phi(e)})$ for all $e\in E(H)$. We prove that for $|V|=s\geq 3$ and $\delta(G_i)\geq s/2$ for each $i\in [s]$, there exists a $\mathbf{G}$-transversal that is a Hamilton cycle. This confirms a conjecture of Aharoni. We also prove an analogous result for perfect matchings.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1910.01281
Document Type :
Working Paper
Full Text :
https://doi.org/10.1112/blms.12343