Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T11:51:53.968Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  30 October 2020

Stefan Ehard
Affiliation:
Institut für Optimierung und Operations Research, Universität Ulm, Germany; stefan.ehard@uni-ulm.de
Stefan Glock
Affiliation:
Institute for Theoretical Studies, ETH Zürich, Switzerland; stefan.glock@eth-its.ethz.ch
Felix Joos
Affiliation:
Institut für Informatik, Universität Heidelberg, Germany; joos@informatik.uni-heidelberg.de

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Discrete Mathematics
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s), 2020. Published by Cambridge University Press