Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRainbow trees in uniformly edge-coloured graphs
78
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 $G(n,p)$ we can find three monochromatic trees such that their union covers all vertices. This improves, for three colours, a result of Bucic, Korandi and Sudakov.
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 size at most $n/2$, then $G$ has at least $lfloor n/(Clog n)rfloor$ edge-disjoint rainbow spanning trees. Here we strengthen this result by showing that if $G$ is any edge-colored graph with $n$ vertices in which each color appears on at most $deltacdotlambda_1/2$ edges, where $deltageq Clog n$ for $n$ and $C$ sufficiently large and $lambda_1$ is the second-smallest eigenvalue of the normalized Laplacian matrix of $G$, then $G$ contains at least $leftlfloorfrac{deltacdotlambda_1}{Clog n}rightrfloor$ edge-disjoint rainbow spanning trees.
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 two adjacent edges have the same colour. In this paper, we show that, for any $varepsilon >0$ and $n$ large, every edge-coloured graph $G$ with $delta^c(G) ge (1/2+varepsilon)n$ contains a properly coloured cycle of length at least $min{ n , lfloor 2 delta^c(G)/3 rfloor}$.
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 maximum number of colors in an edge-coloring of $G$ containing no $t$ edge-disjoint rainbow spanning trees. For any vertex partition $P$, let $E(P,G)$ be the set of non-crossing edges in $G$ with respect to $P$. In this paper, we determine $r(G,t)$ for all host graphs $G$: $r(G,t)=|E(G)|$ if there exists a partition $P_0$ with $|E(G)|-|E(P_0,G)|<t(|P_0|-1)$; and $r(G,t)=max_{Pcolon |P|geq 3} {|E(P,G)|+t(|P|-2)}$ otherwise. As a corollary, we determine $r(K_{p,q},t)$ for all values of $p,q, t$, improving a result of Jia, Lu and Zhang.
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-coloured graphs arising from assigning each edge of the random perturbation $G cup mathbb{G}(n,p)$ a colour, chosen independently and uniformly at random from a set of colours of size $r := r(n)$. We prove that such edge-coloured graph distributions a.a.s. admit rainbow Hamilton cycles whenever the edge-density of the random perturbation satisfies $p := p(n) geq C/n$, for some fixed $C > 0$, and $r = (1 + o(1))n$. The number of colours used is clearly asymptotically best possible. In particular, this improves upon a recent result of Anastos and Frieze (2019) in this regard. As an intermediate result, which may be of independent interest, we prove that randomly edge-coloured sparse pseudo-random graphs a.a.s. admit an almost spanning rainbow path.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
