On a rainbow version of Dirac's theorem
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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article (Journal) Chapter/Article |
| Language: | English |
| Published: |
3 Oct 2019
|
| In: |
Arxiv
Year: 2019, Pages: 1-6 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: http://arxiv.org/abs/1910.01281
|
| Author Notes: | Felix Joos and Jaehoon Kim |
| Summary: | 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. |
|---|---|
| Item Description: | Identifizierung der Ressource nach: 15 Apr 2020 Gesehen am 27.07.2022 |
| Physical Description: | Online Resource |