Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAlmost all optimally coloured complete graphs contain a rainbow Hamilton path
230
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A subgraph $H$ of an edge-coloured graph is called rainbow if all of the edges of $H$ have different colours. In 1989, Andersen conjectured that every proper edge-colouring of $K_{n}$ admits a rainbow path of length $n-2$. We show that almost all optimal edge-colourings of $K_{n}$ admit both (i) a rainbow Hamilton path and (ii) a rainbow cycle using all of the colours. This result demonstrates that Andersens Conjecture holds for almost all optimal edge-colourings of $K_{n}$ and answers a recent question of Ferber, Jain, and Sudakov. Our result also has applications to the existence of transversals in random symmetric Latin squares.
rate research
Read More
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.
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.
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 Komlos, Sarkozy and Szemeredi 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.
Let $G$ be a graph of order $n$ with an edge-coloring $c$, and let $delta^c(G)$ denote the minimum color-degree of $G$. A subgraph $F$ of $G$ is called rainbow if any two edges of $F$ have distinct colors. There have been a lot results in the existing literature on rainbow triangles in edge-colored complete graphs. Fujita and Magnant showed that for an edge-colored complete graph $G$ of order $n$, if $delta^c(G)geq frac{n+1}{2}$, then every vertex of $G$ is contained in a rainbow triangle. In this paper, we show that if $delta^c(G)geq frac{n+k}{2}$, then every vertex of $G$ is contained in at least $k$ rainbow triangles, which can be seen as a generalization of their result. Li showed that for an edge-colored graph $G$ of order $n$, if $delta^c(G)geq frac{n+1}{2}$, then $G$ contains a rainbow triangle. We show that if $G$ is complete and $delta^c(G)geq frac{n}{2}$, then $G$ contains a rainbow triangle and the bound is sharp. Hu et al. showed that for an edge-colored graph $G$ of order $ngeq 20$, if $delta^c(G)geq frac{n+2}{2}$, then $G$ contains two vertex-disjoint rainbow triangles. We show that if $G$ is complete with order $ngeq 8$ and $delta^c(G)geq frac{n+1}{2}$, then $G$ contains two vertex-disjoint rainbow triangles. Moreover, we improve the result of Hu et al. from $ngeq 20$ to $ngeq 7$, the best possible.
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}$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
