2019/07/23 by Ehard, Stefan, Glock, Stefan, Joos, Felix · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1907.09950
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.