Rainbow spanning subgraphs in bounded edge–colourings of graphs with large minimum degree
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||Probabilistic method, Rainbow subgraphs, Switching techniques|
|Journal||Electronic Notes in Discrete Mathematics|
Cano, P. (Pilar), Perarnau, G. (Guillem), & Serra, O. (Oriol). (2017). Rainbow spanning subgraphs in bounded edge–colourings of graphs with large minimum degree. Electronic Notes in Discrete Mathematics, 61, 199–205. doi:10.1016/j.endm.2017.06.039