ﻻ يوجد ملخص باللغة العربية
We obtain sufficient conditions for the emergence of spanning and almost-spanning bounded-degree {sl rainbow} trees in various host graphs, having their edges coloured independently and uniformly at random, using a predetermined palette. Our first result asserts that a uniform colouring of $mathbb{G}(n,omega(1)/n)$, using a palette of size $n$, a.a.s. admits a rainbow copy of any given bounded-degree tree on at most $(1-varepsilon)n$ vertices, where $varepsilon > 0$ is arbitrarily small yet fixed. This serves as a rainbow variant of a classical result by Alon, Krivelevich, and Sudakov pertaining to the embedding of bounded-degree almost-spanning prescribed trees in $mathbb{G}(n,C/n)$, where $C > 0$ is independent of $n$. Given an $n$-vertex graph $G$ with minimum degree at least $delta n$, where $delta > 0$ is fixed, we use our aforementioned result in order to prove that a uniform colouring of the randomly perturbed graph $G cup mathbb{G}(n,omega(1)/n)$, using $(1+alpha)n$ colours, where $alpha > 0$ is arbitrarily small yet fixed, a.a.s. admits a rainbow copy of any given bounded-degree {sl spanning} tree. This can be viewed as a rainbow variant of a result by Krivelevich, Kwan, and Sudakov who proved that $G cup mathbb{G}(n,C/n)$, where $C > 0$ is independent of $n$, a.a.s. admits a copy of any given bounded-degree spanning tree. Finally, and with $G$ as above, we prove that a uniform colouring of $G cup mathbb{G}(n,omega(n^{-2}))$ using $n-1$ colours a.a.s. admits a rainbow spanning tree. Put another way, the trivial lower bound on the size of the palette required for supporting a rainbow spanning tree is also sufficient, essentially as soon as the random perturbation a.a.s. has edges.
We investigate the problem of determining how many monochromatic trees are necessary to cover the vertices of an edge-coloured random graph. More precisely, we show that for $pgg n^{-1/6}{(ln n)}^{1/6}$, in any $3$-edge-colouring of the random graph
A rainbow spanning tree in an edge-colored graph is a spanning tree in which each edge is a different color. Carraher, Hartke, and Horn showed that for $n$ and $C$ large enough, if $G$ is an edge-colored copy of $K_n$ in which each color class has si
Let $G$ be an edge-coloured graph. The minimum colour degree $delta^c(G)$ of $G$ is the largest integer $k$ such that, for every vertex $v$, there are at least $k$ distinct colours on edges incident to $v$. We say that $G$ is properly coloured if no
An edge-colored graph $G$ is called textit{rainbow} if every edge of $G$ receives a different color. Given any host graph $G$, the textit{anti-Ramsey} number of $t$ edge-disjoint rainbow spanning trees in $G$, denoted by $r(G,t)$, is defined as the m
Given an $n$-vertex graph $G$ with minimum degree at least $d n$ for some fixed $d > 0$, the distribution $G cup mathbb{G}(n,p)$ over the supergraphs of $G$ is referred to as a (random) {sl perturbation} of $G$. We consider the distribution of edge-c