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

Pilar Cano, Guillem Perarnau, Oriol Serra

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)
71 Downloads (Pure)

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

Keywords

  • Probabilistic method
  • Rainbow subgraphs
  • Switching techniques

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Rainbow spanning subgraphs in bounded edge–colourings of graphs with large minimum degree'. Together they form a unique fingerprint.

Cite this