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

Felix Joos; Stefan Ehard; Stefan Glock

arxiv: 1907.09950 · v1 · pith:FLL7KWTVnew · submitted 2019-07-23 · 🧮 math.CO

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

Stefan Ehard , Stefan Glock , Felix Joos This is my paper

Pith reviewed 2026-05-24 17:26 UTC · model grok-4.3

classification 🧮 math.CO

keywords rainbow subgraphblow-up lemmaedge-coloringquasirandom graphspanning subgraphgraph decompositionbounded degree

0 comments

The pith

A rainbow blow-up lemma holds for edge-colorings that are almost optimally bounded.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a rainbow analogue of the Komlós–Sárközy–Szemerédi blow-up lemma that remains valid when the host graph's edge-coloring obeys a boundedness condition that is asymptotically tight. Under this condition, any quasirandom graph contains a rainbow copy of every spanning subgraph whose maximum degree is bounded by a constant. Sympathetic readers would care because the result transfers classical embedding power into the rainbow setting and immediately yields consequences for decompositions, orthogonal double covers, and labellings without requiring substantially stronger coloring hypotheses.

Core claim

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.

What carries the argument

The rainbow blow-up lemma, which embeds rainbow copies of bounded-degree graphs into dense quasirandom hosts whose edges satisfy an asymptotically tight per-color bound.

If this is right

Any quasirandom graph whose edges are colored under the stated boundedness condition contains a rainbow copy of every bounded-degree spanning subgraph.
The lemma supplies rainbow versions of many classical embedding results used in graph decompositions.
It yields new existence statements for orthogonal double covers via the same embedding mechanism.
It produces rainbow embeddings that can be repurposed for certain graph-labelling problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same boundedness condition may suffice for rainbow versions of other embedding lemmas that currently require stricter color restrictions.
One could check the result numerically on small random regular graphs to see how close the boundedness threshold must be in practice.
The technique might extend to hypergraph embeddings or to settings where only a fraction of the edges need to be rainbow.

Load-bearing premise

The edge-colouring must obey a per-color boundedness condition that is asymptotically the strongest possible for the embedding statement to remain true.

What would settle it

An explicit quasirandom graph together with an edge-coloring in which some color appears on more than the allowed number of edges (by a constant factor) yet no rainbow copy of a fixed bounded-degree spanning subgraph exists would refute the claim.

Figures

Figures reproduced from arXiv: 1907.09950 by Felix Joos, Stefan Ehard, Stefan Glock.

**Figure 1.** Figure 1: If x0 is mapped to v0 by σ, then only those candidates of xi remain that are neighbours of v0. Moreover, colour α of the edge v0vj is added to the the candidate edge xj vj , which captures the information that if xj is later embedded at vj , then this embedding uses α. We say that (H, G,(Ai)i∈[r]0 , c) is an (ε,(d G i )i∈[r] ,(di)i∈[r]0 , t,Λ)-embedding-instance if in addition, we have that • G[V0, Vi ] i… view at source ↗

read the original 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\'os, S\'ark\"ozy and Szemer\'edi 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a rainbow blow-up lemma that works for colorings with bounds nearly matching the classical non-rainbow case, which strengthens the corollary on rainbow spanning subgraphs in quasirandom hosts.

read the letter

The main thing to know is that this extends the Komlós-Sárközy-Szemerédi blow-up lemma to the rainbow setting while keeping the coloring bound asymptotically optimal for the intended applications. That bound improvement is the concrete advance over prior rainbow versions, which needed stricter conditions on color repetition. The corollary then follows directly: any bounded-degree spanning H has a rainbow copy in a quasirandom G when the edge-coloring of G meets that near-optimal density restriction on each color class. The abstract also flags uses in decompositions, orthogonal double covers, and labellings, which line up with how these lemmas get applied elsewhere. The work looks technically direct, building on the standard regularity-plus-embedding template without obvious new machinery or circular steps. The boundedness condition is presented as best possible, which would make the result sharp enough to be cited in follow-up papers on rainbow embeddings. A minor soft spot is that the abstract alone does not show the proof details or constant losses, so it is hard to judge how much room remains for further tightening or whether the quasirandom assumption hides extra technical cost. Still, nothing in the stated claim suggests an internal gap or unsupported reduction. This is for people already working with blow-up lemmas in extremal graph theory or rainbow decompositions. If you use these tools, the improved bound is worth seeing in full. It deserves peer review because the result is stated cleanly and targets a practical limitation in the existing rainbow toolkit.

Referee Report

0 major / 2 minor

Summary. The manuscript proves a rainbow version of the Komlós–Sárközy–Szemerédi blow-up lemma that holds for edge-colourings satisfying an asymptotically optimal boundedness condition. As a corollary, any bounded-degree spanning subgraph H admits a rainbow copy in a quasirandom host G under this colouring condition. The result is stated to have further applications to graph decompositions, orthogonal double covers and graph labellings.

Significance. If the central lemma holds, the work supplies a flexible embedding tool for rainbow problems at the natural density threshold. The optimality claim on the boundedness condition strengthens the result relative to earlier rainbow blow-up statements and directly supports the corollary on spanning subgraphs in quasirandom graphs.

minor comments (2)

[Abstract] The abstract refers to an 'almost optimally bounded' colouring without stating the precise quantitative condition; the introduction or statement of the main lemma should give the exact bound (e.g., maximum colour degree o(n) or similar) so that the optimality claim can be verified immediately.
[Section 2] Notation for the host graph G, the colouring, and the blow-up parameters should be introduced uniformly in §2 before the statement of the main lemma; occasional reuse of symbols from the classical blow-up lemma risks confusion.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript, the supportive summary of its contributions, and the recommendation for minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; direct proof of extended lemma

full rationale

The paper states a direct proof of a rainbow blow-up lemma extending the Komlós-Sárközy-Szemerédi result to almost optimally bounded edge-colourings, with a corollary for rainbow spanning subgraphs in quasirandom hosts. No self-definitional relations, fitted inputs renamed as predictions, load-bearing self-citations, uniqueness theorems imported from the authors' prior work, smuggled ansatzes, or renamings of known results appear in the abstract or claim structure. The boundedness condition is presented as an external asymptotic optimality assumption rather than an internal fit. The derivation chain is therefore self-contained as a mathematical existence proof.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, invented entities, or ad-hoc axioms; the work rests on the classical blow-up lemma and standard quasirandomness assumptions.

axioms (2)

standard math The blow-up lemma of Komlós, Sárközy and Szemerédi
The new rainbow version is stated as an extension of this prior result.
domain assumption Quasirandomness of the host graph G
Invoked for the corollary on spanning rainbow copies.

pith-pipeline@v0.9.0 · 5632 in / 1274 out tokens · 103643 ms · 2026-05-24T17:26:24.911340+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

43 extracted references · 43 canonical work pages · 3 internal anchors

[1]

Adamaszek, P

A. Adamaszek, P. Allen, C. Grosu, and J. Hladk´ y, Almost all trees are almost graceful , arXiv:1608.01577 (2016)

work page arXiv 2016
[2]

Albert, A

M. Albert, A. Frieze, and B. Reed, Multicoloured Hamilton cycles , Electron. J. Combin. 2 (1995), Art. 10, 13 pages

work page 1995
[3]

Perfectly packing graphs with bounded degeneracy and many leaves

P. Allen, J. B¨ ottcher, D. Clemens, and A. Taraz, Perfectly packing graphs with bounded degeneracy and many leaves, arXiv:1906.11558 (2019)

work page internal anchor Pith review Pith/arXiv arXiv 1906
[4]

Allen, J

P. Allen, J. B¨ ottcher, H. H` an, Y. Kohayakawa, and Y. Per son, Blow-up lemmas for sparse graphs , arXiv:1612.00622 (2016)

work page arXiv 2016
[5]

Allen, J

P. Allen, J. B¨ ottcher, J. Hladk´ y, and D. Piguet, Packing degenerate graphs , Adv. Math. (to appear)

work page
[6]

B¨ ottcher, Y

J. B¨ ottcher, Y. Kohayakawa, and A. Procacci, Properly coloured copies and rainbow copies of large graphs with small maximum degree , Random Structures Algorithms 40 (2012), 425–436

work page 2012
[7]

B¨ ottcher, Y

J. B¨ ottcher, Y. Kohayakawa, A. Taraz, and A. W¨ urﬂ, An extension of the blow-up lemma to arrangeable graphs, SIAM J. Discrete Math. 29 (2015), 962–1001

work page 2015
[8]

B¨ ottcher, M

J. B¨ ottcher, M. Schacht, and A. Taraz, Proof of the bandwidth conjecture of Bollob´ as and Koml´ os, Math. Ann. 343 (2009), 175–205

work page 2009
[9]

Coulson and G

M. Coulson and G. Perarnau, Rainbow matchings in Dirac bipartite graphs , Random Structures Algorithms (to appear)

work page
[10]

Csaba, On the Bollob´ as-Eldridge conjecture for bipartite graphs , Combin

B. Csaba, On the Bollob´ as-Eldridge conjecture for bipartite graphs , Combin. Probab. Comput. 16 (2007), 661–691

work page 2007
[11]

Drmota and A

M. Drmota and A. Llad´ o, Almost every tree with m edges decomposes K2m,2m, Combin. Probab. Comput. 23 (2014), 50–65

work page 2014
[12]

R. A. Duke, H. Lefmann, and V. R¨ odl, A fast approximation algorithm for computing the frequenci es of subgraphs in a given graph , SIAM J. Comput. 24 (1995), 598–620

work page 1995
[13]

Ehard, S

S. Ehard, S. Glock, and F. Joos, Pseudorandom hypergraph matchings , preprint (2019)

work page 2019
[14]

Erd˝ os, J

P. Erd˝ os, J. Neˇ setˇ ril, and V. R¨ odl,On some problems related to partitions of edges of a graph , Graphs and other combinatorial topics, Teubner-Texte Math. 59, Teubn er, 1983, pp. 54–63

work page 1983
[15]

J. A. Gallian, A dynamic survey of graph labeling , Electron. J. Combin. 5 (1998), Dynamic Survey 6, 43

work page 1998
[16]

A rainbow blow-up lemma

S. Glock and F. Joos, A rainbow blow-up lemma , arXiv:1802.07700 (2018). 28 S. EHARD, S. GLOCK, AND F. JOOS

work page internal anchor Pith review Pith/arXiv arXiv 2018
[17]

Glock, F

S. Glock, F. Joos, J. Kim, D. K¨ uhn, and D. Osthus, Resolution of the Oberwolfach problem , arXiv:1806.04644 (2018)

work page arXiv 2018
[18]

Glock, D

S. Glock, D. K¨ uhn, A. Lo, and D. Osthus, The existence of designs via iterative absorption , arXiv:1611.06827 (2016)

work page arXiv 2016
[19]

, Hypergraph F -designs for arbitrary F , arXiv:1706.01800 (2017)

work page arXiv 2017
[20]

R. L. Graham and N. J. A. Sloane, On additive bases and harmonious graphs , SIAM J. Algebraic Discrete Methods 1 (1980), 382–404

work page 1980
[21]

H.-D. O. F. Gronau, R. C. Mullin, and A. Rosa, Orthogonal double covers of complete graphs by trees , Graphs Combin. 13 (1997), 251–262

work page 1997
[22]

Hajnal and E

A. Hajnal and E. Szemer´ edi, Proof of a conjecture of Erd˝ os, In: Combinatorial Theory and its Applications II (P. Erd˝ os, A. R´ enyi, and V.T. S´ os, eds.), North Holland, 1970, pp. 601–623

work page 1970
[23]

Janson, T

S. Janson, T. /suppress Luczak, and A. Ruci´ nski,Random graphs, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley- Interscience, 2000

work page 2000
[24]

F. Joos, J. Kim, D. K¨ uhn, and D. Osthus, Optimal packings of bounded degree trees , J. Eur. Math. Soc. (to appear)

work page
[25]

Keevash, A hypergraph blow-up lemma , Random Structures Algorithms 39 (2011), 275–376

P. Keevash, A hypergraph blow-up lemma , Random Structures Algorithms 39 (2011), 275–376

work page 2011
[26]

, The existence of designs , arXiv:1401.3665 (2014)

work page arXiv 2014
[27]

, The existence of designs II , arXiv:1802.05900 (2018)

work page internal anchor Pith review Pith/arXiv arXiv 2018
[28]

J. Kim, D. K¨ uhn, A. Kupavskii, and D. Osthus, Rainbow structures in locally bounded colourings of graphs , arXiv:1805.08424 (2018)

work page arXiv 2018
[29]

J. Kim, D. K¨ uhn, D. Osthus, and M. Tyomkyn, A blow-up lemma for approximate decompositions , Trans. Amer. Math. Soc. 371 (2019), 4655–4742

work page 2019
[30]

Koml´ os, G

J. Koml´ os, G. N. S´ ark¨ ozy, and E. Szemer´ edi,Blow-up lemma , Combinatorica 17 (1997), 109–123

work page 1997
[31]

Graph Theory 29 (1998), 167–176

, On the P´ osa-Seymour conjecture, J. Graph Theory 29 (1998), 167–176

work page 1998
[32]

, Proof of the Seymour conjecture for large graphs , Ann. Comb. 2 (1998), 43–60

work page 1998
[33]

235 (2001), 255–269

, Proof of the Alon-Yuster conjecture , Discrete Math. 235 (2001), 255–269

work page 2001
[34]

Kotzig, On certain vertex-valuations of ﬁnite graphs , Utilitas Math

A. Kotzig, On certain vertex-valuations of ﬁnite graphs , Utilitas Math. 4 (1973), 261–290

work page 1973
[35]

K¨ uhn and D

D. K¨ uhn and D. Osthus, The minimum degree threshold for perfect graph packings , Combinatorica 29 (2009), 65–107

work page 2009
[36]

, Hamilton decompositions of regular expanders: A proof of Ke lly’s conjecture for large tournaments , Adv. Math. 237 (2013), 62–146

work page 2013
[37]

McDiarmid, On the method of bounded diﬀerences , Surveys in combinatorics, 1989 (Norwich, 1989), London Math

C. McDiarmid, On the method of bounded diﬀerences , Surveys in combinatorics, 1989 (Norwich, 1989), London Math. Soc. Lecture Note Ser. 141, Cambridge Univ. Pre ss, 1989, pp. 148–188

work page 1989
[38]

Montgomery, A

R. Montgomery, A. Pokrovskiy, and B. Sudakov, Decompositions into spanning rainbow structures , Proc. Lond. Math. Soc. 119 (2019), 899–959

work page 2019
[39]

, Embedding rainbow trees with applications to graph labelli ng and decomposition , J. Eur. Math. Soc. (to appear)

work page
[40]

R¨ odl, On a packing and covering problem , European J

V. R¨ odl, On a packing and covering problem , European J. Combin. 6 (1985), 69–78

work page 1985
[41]

R¨ odl and A

V. R¨ odl and A. Ruci´ nski,Perfect matchings in ǫ-regular graphs and the blow-up lemma , Combinatorica 19 (1999), 437–452

work page 1999
[42]

Rosa, On certain valuations of the vertices of a graph , Theory of Graphs (Internat

A. Rosa, On certain valuations of the vertices of a graph , Theory of Graphs (Internat. Sympos., Rome, 1966), Gordon and Breach, New York; Dunod, Paris, 1967, pp. 3 49–355

work page 1966
[43]

˙Zak, Harmonious order of graphs , Discrete Math

A. ˙Zak, Harmonious order of graphs , Discrete Math. 309 (2009), 6055–6064. (S. Ehard) Institut f ¨ur Optimierung und Operations Research, Universit ¨at Ulm, Ulm, Germany E-mail address : stefan.ehard@uni-ulm.de (S. Glock, F. Joos) School of Mathematics, University of Birmingham, Edgbasto n, Birmingham, B15 2TT, United Kingdom E-mail address : [s.glock, f...

work page 2009

[1] [1]

Adamaszek, P

A. Adamaszek, P. Allen, C. Grosu, and J. Hladk´ y, Almost all trees are almost graceful , arXiv:1608.01577 (2016)

work page arXiv 2016

[2] [2]

Albert, A

M. Albert, A. Frieze, and B. Reed, Multicoloured Hamilton cycles , Electron. J. Combin. 2 (1995), Art. 10, 13 pages

work page 1995

[3] [3]

Perfectly packing graphs with bounded degeneracy and many leaves

P. Allen, J. B¨ ottcher, D. Clemens, and A. Taraz, Perfectly packing graphs with bounded degeneracy and many leaves, arXiv:1906.11558 (2019)

work page internal anchor Pith review Pith/arXiv arXiv 1906

[4] [4]

Allen, J

P. Allen, J. B¨ ottcher, H. H` an, Y. Kohayakawa, and Y. Per son, Blow-up lemmas for sparse graphs , arXiv:1612.00622 (2016)

work page arXiv 2016

[5] [5]

Allen, J

P. Allen, J. B¨ ottcher, J. Hladk´ y, and D. Piguet, Packing degenerate graphs , Adv. Math. (to appear)

work page

[6] [6]

B¨ ottcher, Y

J. B¨ ottcher, Y. Kohayakawa, and A. Procacci, Properly coloured copies and rainbow copies of large graphs with small maximum degree , Random Structures Algorithms 40 (2012), 425–436

work page 2012

[7] [7]

B¨ ottcher, Y

J. B¨ ottcher, Y. Kohayakawa, A. Taraz, and A. W¨ urﬂ, An extension of the blow-up lemma to arrangeable graphs, SIAM J. Discrete Math. 29 (2015), 962–1001

work page 2015

[8] [8]

B¨ ottcher, M

J. B¨ ottcher, M. Schacht, and A. Taraz, Proof of the bandwidth conjecture of Bollob´ as and Koml´ os, Math. Ann. 343 (2009), 175–205

work page 2009

[9] [9]

Coulson and G

M. Coulson and G. Perarnau, Rainbow matchings in Dirac bipartite graphs , Random Structures Algorithms (to appear)

work page

[10] [10]

Csaba, On the Bollob´ as-Eldridge conjecture for bipartite graphs , Combin

B. Csaba, On the Bollob´ as-Eldridge conjecture for bipartite graphs , Combin. Probab. Comput. 16 (2007), 661–691

work page 2007

[11] [11]

Drmota and A

M. Drmota and A. Llad´ o, Almost every tree with m edges decomposes K2m,2m, Combin. Probab. Comput. 23 (2014), 50–65

work page 2014

[12] [12]

R. A. Duke, H. Lefmann, and V. R¨ odl, A fast approximation algorithm for computing the frequenci es of subgraphs in a given graph , SIAM J. Comput. 24 (1995), 598–620

work page 1995

[13] [13]

Ehard, S

S. Ehard, S. Glock, and F. Joos, Pseudorandom hypergraph matchings , preprint (2019)

work page 2019

[14] [14]

Erd˝ os, J

P. Erd˝ os, J. Neˇ setˇ ril, and V. R¨ odl,On some problems related to partitions of edges of a graph , Graphs and other combinatorial topics, Teubner-Texte Math. 59, Teubn er, 1983, pp. 54–63

work page 1983

[15] [15]

J. A. Gallian, A dynamic survey of graph labeling , Electron. J. Combin. 5 (1998), Dynamic Survey 6, 43

work page 1998

[16] [16]

A rainbow blow-up lemma

S. Glock and F. Joos, A rainbow blow-up lemma , arXiv:1802.07700 (2018). 28 S. EHARD, S. GLOCK, AND F. JOOS

work page internal anchor Pith review Pith/arXiv arXiv 2018

[17] [17]

Glock, F

S. Glock, F. Joos, J. Kim, D. K¨ uhn, and D. Osthus, Resolution of the Oberwolfach problem , arXiv:1806.04644 (2018)

work page arXiv 2018

[18] [18]

Glock, D

S. Glock, D. K¨ uhn, A. Lo, and D. Osthus, The existence of designs via iterative absorption , arXiv:1611.06827 (2016)

work page arXiv 2016

[19] [19]

, Hypergraph F -designs for arbitrary F , arXiv:1706.01800 (2017)

work page arXiv 2017

[20] [20]

R. L. Graham and N. J. A. Sloane, On additive bases and harmonious graphs , SIAM J. Algebraic Discrete Methods 1 (1980), 382–404

work page 1980

[21] [21]

H.-D. O. F. Gronau, R. C. Mullin, and A. Rosa, Orthogonal double covers of complete graphs by trees , Graphs Combin. 13 (1997), 251–262

work page 1997

[22] [22]

Hajnal and E

A. Hajnal and E. Szemer´ edi, Proof of a conjecture of Erd˝ os, In: Combinatorial Theory and its Applications II (P. Erd˝ os, A. R´ enyi, and V.T. S´ os, eds.), North Holland, 1970, pp. 601–623

work page 1970

[23] [23]

Janson, T

S. Janson, T. /suppress Luczak, and A. Ruci´ nski,Random graphs, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley- Interscience, 2000

work page 2000

[24] [24]

F. Joos, J. Kim, D. K¨ uhn, and D. Osthus, Optimal packings of bounded degree trees , J. Eur. Math. Soc. (to appear)

work page

[25] [25]

Keevash, A hypergraph blow-up lemma , Random Structures Algorithms 39 (2011), 275–376

P. Keevash, A hypergraph blow-up lemma , Random Structures Algorithms 39 (2011), 275–376

work page 2011

[26] [26]

, The existence of designs , arXiv:1401.3665 (2014)

work page arXiv 2014

[27] [27]

, The existence of designs II , arXiv:1802.05900 (2018)

work page internal anchor Pith review Pith/arXiv arXiv 2018

[28] [28]

J. Kim, D. K¨ uhn, A. Kupavskii, and D. Osthus, Rainbow structures in locally bounded colourings of graphs , arXiv:1805.08424 (2018)

work page arXiv 2018

[29] [29]

J. Kim, D. K¨ uhn, D. Osthus, and M. Tyomkyn, A blow-up lemma for approximate decompositions , Trans. Amer. Math. Soc. 371 (2019), 4655–4742

work page 2019

[30] [30]

Koml´ os, G

J. Koml´ os, G. N. S´ ark¨ ozy, and E. Szemer´ edi,Blow-up lemma , Combinatorica 17 (1997), 109–123

work page 1997

[31] [31]

Graph Theory 29 (1998), 167–176

, On the P´ osa-Seymour conjecture, J. Graph Theory 29 (1998), 167–176

work page 1998

[32] [32]

, Proof of the Seymour conjecture for large graphs , Ann. Comb. 2 (1998), 43–60

work page 1998

[33] [33]

235 (2001), 255–269

, Proof of the Alon-Yuster conjecture , Discrete Math. 235 (2001), 255–269

work page 2001

[34] [34]

Kotzig, On certain vertex-valuations of ﬁnite graphs , Utilitas Math

A. Kotzig, On certain vertex-valuations of ﬁnite graphs , Utilitas Math. 4 (1973), 261–290

work page 1973

[35] [35]

K¨ uhn and D

D. K¨ uhn and D. Osthus, The minimum degree threshold for perfect graph packings , Combinatorica 29 (2009), 65–107

work page 2009

[36] [36]

, Hamilton decompositions of regular expanders: A proof of Ke lly’s conjecture for large tournaments , Adv. Math. 237 (2013), 62–146

work page 2013

[37] [37]

McDiarmid, On the method of bounded diﬀerences , Surveys in combinatorics, 1989 (Norwich, 1989), London Math

C. McDiarmid, On the method of bounded diﬀerences , Surveys in combinatorics, 1989 (Norwich, 1989), London Math. Soc. Lecture Note Ser. 141, Cambridge Univ. Pre ss, 1989, pp. 148–188

work page 1989

[38] [38]

Montgomery, A

R. Montgomery, A. Pokrovskiy, and B. Sudakov, Decompositions into spanning rainbow structures , Proc. Lond. Math. Soc. 119 (2019), 899–959

work page 2019

[39] [39]

, Embedding rainbow trees with applications to graph labelli ng and decomposition , J. Eur. Math. Soc. (to appear)

work page

[40] [40]

R¨ odl, On a packing and covering problem , European J

V. R¨ odl, On a packing and covering problem , European J. Combin. 6 (1985), 69–78

work page 1985

[41] [41]

R¨ odl and A

V. R¨ odl and A. Ruci´ nski,Perfect matchings in ǫ-regular graphs and the blow-up lemma , Combinatorica 19 (1999), 437–452

work page 1999

[42] [42]

Rosa, On certain valuations of the vertices of a graph , Theory of Graphs (Internat

A. Rosa, On certain valuations of the vertices of a graph , Theory of Graphs (Internat. Sympos., Rome, 1966), Gordon and Breach, New York; Dunod, Paris, 1967, pp. 3 49–355

work page 1966

[43] [43]

˙Zak, Harmonious order of graphs , Discrete Math

A. ˙Zak, Harmonious order of graphs , Discrete Math. 309 (2009), 6055–6064. (S. Ehard) Institut f ¨ur Optimierung und Operations Research, Universit ¨at Ulm, Ulm, Germany E-mail address : stefan.ehard@uni-ulm.de (S. Glock, F. Joos) School of Mathematics, University of Birmingham, Edgbasto n, Birmingham, B15 2TT, United Kingdom E-mail address : [s.glock, f...

work page 2009