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

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.

Keywords

• 05C15
• 05C35
• 05C51
• 05C60
• 05C70
• 05C78
• 05B40
• blow-up lemma
• rainbow colourings