For a given $\delta \in (0,1)$, the randomly perturbed graph model is defined as the union of any $n$-vertex graph $G_0$ with minimum degree $\delta n$ and the binomial random graph $\mathbf{G}(n,p)$ on the same vertex set. Moreover, we say that a graph is uniformly coloured with colours in $\mathcal{C}$ if each edge is coloured independently and uniformly at random with a colour from $\mathcal{C}$.
Based on a coupling idea of McDiarmid, we provide a general tool to tackle problems concerning finding a rainbow copy of a graph $H=H(n)$ in a uniformly coloured perturbed $n$-vertex graph with colours in $[(1+o(1))e(H)]$. For example, our machinery easily allows to recover a result of Aigner-Horev and Hefetz concerning rainbow Hamilton cycles, and to improve a result of Aigner-Horev, Hefetz and Lahiri concerning rainbow bounded-degree spanning trees.
Furthermore, using different methods, we prove that for any $\delta \in (0,1)$ and integer $d \ge 2$, there exists $C=C(\delta ,d)>0$ such that the following holds. Let $T$ be a tree on $n$ vertices with maximum degree at most $d$ and $G_0$ be an $n$-vertex graph with $\delta (G_0)\ge \delta n$. Then a uniformly coloured $G_0 \cup \mathbf{G}(n,C/n)$ with colours in $[n-1]$ contains a rainbow copy of $T$ with high probability. This is optimal both in terms of colours and edge probability (up to a constant factor).
Accepted:
Published online:
Keywords: Randomly perturbed graphs, Rainbow subgraphs, Coupling, Trees
Katsamaktsis, Kyriakos 1; Letzter, Shoham 1; Sgueglia, Amedeo 2
CC-BY 4.0
@article{IGT_2025__2__245_0,
author = {Katsamaktsis, Kyriakos and Letzter, Shoham and Sgueglia, Amedeo},
title = {Rainbow subgraphs of uniformly coloured randomly perturbed graphs},
journal = {Innovations in Graph Theory},
pages = {245--273},
year = {2025},
publisher = {Stichting Innovations in Graph Theory},
volume = {2},
doi = {10.5802/igt.12},
language = {en},
url = {https://igt.centre-mersenne.org/articles/10.5802/igt.12/}
}
TY - JOUR AU - Katsamaktsis, Kyriakos AU - Letzter, Shoham AU - Sgueglia, Amedeo TI - Rainbow subgraphs of uniformly coloured randomly perturbed graphs JO - Innovations in Graph Theory PY - 2025 SP - 245 EP - 273 VL - 2 PB - Stichting Innovations in Graph Theory UR - https://igt.centre-mersenne.org/articles/10.5802/igt.12/ DO - 10.5802/igt.12 LA - en ID - IGT_2025__2__245_0 ER -
%0 Journal Article %A Katsamaktsis, Kyriakos %A Letzter, Shoham %A Sgueglia, Amedeo %T Rainbow subgraphs of uniformly coloured randomly perturbed graphs %J Innovations in Graph Theory %D 2025 %P 245-273 %V 2 %I Stichting Innovations in Graph Theory %U https://igt.centre-mersenne.org/articles/10.5802/igt.12/ %R 10.5802/igt.12 %G en %F IGT_2025__2__245_0
Katsamaktsis, Kyriakos; Letzter, Shoham; Sgueglia, Amedeo. Rainbow subgraphs of uniformly coloured randomly perturbed graphs. Innovations in Graph Theory, Volume 2 (2025), pp. 245-273. doi: 10.5802/igt.12
[1] Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs, SIAM J. Discrete Math., Volume 35 (2021) no. 3, pp. 1569-1577 | DOI | Zbl | MR
[2] Rainbow trees in uniformly edge-colored graphs, Random Struct. Algorithms, Volume 62 (2023) no. 2, pp. 287-303 | DOI | Zbl | MR
[3] Embedding nearly-spanning bounded degree trees, Combinatorica, Volume 27 (2007) no. 6, pp. 629-644 | DOI | Zbl | MR
[4] High powers of Hamiltonian cycles in randomly augmented graphs, J. Graph Theory, Volume 98 (2021) no. 2, pp. 255-284 | DOI | Zbl | MR
[5] Powers of Hamiltonian cycles in randomly augmented Dirac graphs—the complete collection, J. Graph Theory, Volume 104 (2023) no. 4, pp. 811-835 | DOI | Zbl | MR
[6] Rainbow matchings and Hamilton cycles in random graphs, Random Struct. Algorithms, Volume 48 (2016) no. 3, pp. 503-523 | DOI | Zbl | MR
[7] Tilings in randomly perturbed dense graphs, Comb. Probab. Comput., Volume 28 (2019) no. 2, pp. 159-176 | DOI | MR | Zbl
[8] How many random edges make a dense graph Hamiltonian?, Random Struct. Algorithms, Volume 22 (2003) no. 1, pp. 33-42 | DOI | Zbl | MR
[9] Universality for bounded degree spanning trees in randomly perturbed graphs, Random Struct. Algorithms, Volume 55 (2019) no. 4, pp. 854-864 | Zbl | MR | DOI
[10] Embedding spanning bounded graphs in randomly perturbed graphs, Mathematika, Volume 66 (2020) no. 2, pp. 422-447 | DOI | Zbl | MR
[11] Triangles in randomly perturbed graphs, Comb. Probab. Comput., Volume 32 (2023) no. 1, pp. 91-121 | DOI | MR | Zbl
[12] The square of a Hamilton cycle in randomly perturbed graphs, Random Struct. Algorithms, Volume 65 (2024) no. 2, pp. 342-386 | DOI | MR | Zbl
[13] Powers of Hamiltonian cycles in randomly augmented graphs, Random Struct. Algorithms, Volume 56 (2020) no. 1, pp. 122-141 | DOI | Zbl | MR
[14] Closing gaps in problems related to Hamilton cycles in random graphs and hypergraphs, Electron. J. Comb., Volume 22 (2015) no. 1, Paper no. 1.61, 7 pages | Zbl | MR
[15] Rainbow Hamilton cycles in random graphs and hypergraphs, Recent trends in combinatorics (The IMA Volumes in Mathematics and its Applications), Volume 159, Springer, 2016, pp. 167-189 | DOI | Zbl
[16] Rainbow Hamilton cycles in random graphs, Random Struct. Algorithms, Volume 44 (2014) no. 3, pp. 328-354 | DOI | Zbl | MR
[17] Almost all optimally coloured complete graphs contain a rainbow Hamilton path, J. Comb. Theory, Ser. B, Volume 156 (2022), pp. 57-100 | DOI | MR | Zbl
[18] Tilings in randomly perturbed graphs: bridging the gap between Hajnal-Szemerédi and Johansson-Kahn-Vu, Random Struct. Algorithms, Volume 58 (2021) no. 3, pp. 480-516 | MR | DOI | Zbl
[19] Random Graphs, John Wiley & Sons, 2011 | MR
[20] Spanning trees in randomly perturbed graphs, Random Struct. Algorithms, Volume 56 (2020) no. 1, pp. 169-219 | DOI | Zbl | MR
[21] Rainbow Hamiltonicity in uniformly coloured perturbed graphs (2023) | arXiv
[22] Rainbow Hamiltonicity in uniformly coloured perturbed digraphs, Comb. Probab. Comput., Volume 33 (2024) no. 5, pp. 624-642 | DOI | MR
[23] Embedding spanning trees in random graphs, SIAM J. Discrete Math., Volume 24 (2010) no. 4, pp. 1495-1500 | DOI | Zbl | MR
[24] Bounded-degree spanning trees in randomly perturbed graphs, SIAM J. Discrete Math., Volume 31 (2017) no. 1, pp. 155-171 | DOI | MR | Zbl
[25] Clutter percolation and random graphs, Math. Program. Study, Volume 13 (1980), pp. 17-25 | Zbl | DOI | MR
[26] Embedding bounded degree spanning trees in random graphs (2014) | arXiv | Zbl
[27] Spanning trees in random graphs, Adv. Math., Volume 356 (2019), Paper no. 106793, 92 pages | DOI | MR | Zbl
[28] Sprinkling a few random edges doubles the power, SIAM J. Discrete Math., Volume 35 (2021) no. 2, pp. 988-1004 | DOI | MR | Zbl
Cited by Sources: