Abstract
We study the existence of rainbow perfect matching and rainbow Hamiltonian cycles in edge–colored graphs where every color appears a bounded number of times. We derive asymptotically tight bounds on the minimum degree of the host graph for the existence of such rainbow spanning structures. The proof uses a probabilisitic argument combined with switching techniques.
Original language | English |
---|---|
Pages (from-to) | 199-205 |
Number of pages | 7 |
Journal | Electronic Notes in Discrete Mathematics |
Volume | 61 |
Early online date | 3 Aug 2017 |
DOIs | |
Publication status | Published - Aug 2017 |
Keywords
- Probabilistic method
- Rainbow subgraphs
- Switching techniques
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics