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

Research output: Contribution to journalArticlepeer-review


Colleges, School and Institutes

External organisations

  • Universitat Politecnica de Catalunya
  • Carleton University


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 languageEnglish
Pages (from-to)199-205
Number of pages7
JournalElectronic Notes in Discrete Mathematics
Early online date3 Aug 2017
Publication statusPublished - Aug 2017


  • Probabilistic method, Rainbow subgraphs, Switching techniques