Article ID Journal Published Year Pages File Type
5777073 Electronic Notes in Discrete Mathematics 2017 7 Pages PDF
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.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
Rainbow spanning subgraphs in bounded edge-colourings of graphs with large minimum degree
Authors
, , ,