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

Pilar Cano; Guillem Perarnau; Oriol Serra

doi:10.1016/j.endm.2017.06.039

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

Pilar Cano, Guillem Perarnau, Oriol Serra

Mathematics

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

118 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 language	English
Pages (from-to)	199-205
Number of pages	7
Journal	Electronic Notes in Discrete Mathematics
Volume	61
Early online date	3 Aug 2017
DOIs	https://doi.org/10.1016/j.endm.2017.06.039
Publication status	Published - Aug 2017

Keywords

Probabilistic method
Rainbow subgraphs
Switching techniques

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.endm.2017.06.039Licence: None: All rights reserved

rainbow_ext_abstractAccepted author manuscript, 204 KBLicence: Creative Commons: Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)

https://www.sciencedirect.com/science/article/pii/S1571065317301245?via%3DihubLicence: None: All rights reserved

Cite this

@article{cbfda47788514f278892eb551aee9b4b,

title = "Rainbow spanning subgraphs in bounded edge–colourings of graphs with large minimum degree",

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 = "Probabilistic method, Rainbow subgraphs, Switching techniques",

author = "Pilar Cano and Guillem Perarnau and Oriol Serra",

year = "2017",

month = aug,

doi = "10.1016/j.endm.2017.06.039",

language = "English",

volume = "61",

pages = "199--205",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

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

AU - Cano, Pilar

AU - Perarnau, Guillem

AU - Serra, Oriol

PY - 2017/8

Y1 - 2017/8

N2 - 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.

AB - 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.

KW - Probabilistic method

KW - Rainbow subgraphs

KW - Switching techniques

UR - http://www.scopus.com/inward/record.url?scp=85026767163&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2017.06.039

DO - 10.1016/j.endm.2017.06.039

M3 - Article

AN - SCOPUS:85026767163

SN - 1571-0653

VL - 61

SP - 199

EP - 205

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this