Rainbow spanning subgraphs in bounded edge–colourings of graphs with large minimum degree

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

External organisations

  • Universitat Politecnica de Catalunya
  • Department of Psychology, Carleton University

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.

Details

Original languageEnglish
Pages (from-to)199-205
Number of pages7
JournalElectronic Notes in Discrete Mathematics
Volume61
Early online date3 Aug 2017
Publication statusPublished - Aug 2017

Keywords

  • Probabilistic method, Rainbow subgraphs, Switching techniques