A rainbow blow-up lemma for almost optimally bounded edge-colourings

• Verfasst von: Ehard, Stefan [VerfasserIn]
• Verfasst von: Glock, Stefan [VerfasserIn]
• Verfasst von: Joos, Felix [VerfasserIn]
• Titel: A rainbow blow-up lemma for almost optimally bounded edge-colourings
• Verf.angabe: Stefan Ehard, Stefan Glock and Felix Joos
• E-Jahr: 2020
• Jahr: 30 October 2020
• Umfang: 32 S.
• Fussnoten: Gesehen am 24.11.2020
• Titel Quelle: Enthalten in: Forum of mathematics. Sigma
• Ort Quelle: Cambridge : Cambridge Univ. Press, 2013
• Jahr Quelle: 2020
• Band/Heft Quelle: 8(2020), Artikel-ID e37, Seite 1-32
• ISSN Quelle: 2050-5094
• DOI: doi:10.1017/fms.2020.38
• Datenträger: Online-Ressource
• Sprache: eng
• Sach-SW: 05B40
• Sach-SW: 05C15
• Sach-SW: 05C35
• Sach-SW: 05C51
• Sach-SW: 05C60
• Sach-SW: 05C70
• Sach-SW: 05C78
• Sach-SW: blow-up lemma
• Sach-SW: rainbow colourings
• K10plus-PPN: 1740776038

Abstract

A subgraph of an edge-coloured graph is called rainbow if all its edges have different colours. We prove a rainbow version of the blow-up lemma of Komlós, Sárközy, and Szemerédi that applies to almost optimally bounded colourings. A corollary of this is that there exists a rainbow copy of any bounded-degree spanning subgraph H in a quasirandom host graph G, assuming that the edge-colouring of G fulfills a boundedness condition that is asymptotically best possible. This has many applications beyond rainbow colourings: for example, to graph decompositions, orthogonal double covers, and graph labellings.