Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLong properly coloured cycles in edge-coloured graphs
121
0
0.0
(
0
)
Authors
Allan Lo
Ask ChatGPT about the research
No Arabic abstract
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}$.
rate research
Read More
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.
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.
Properly colored cycles in edge-colored graphs are closely related to directed cycles in oriented graphs. As an analogy of the well-known Caccetta-H{a}ggkvist Conjecture, we study the existence of properly colored cycles of bounded length in an edge-colored graph. We first prove that for all integers $s$ and $t$ with $tgeq sgeq2$, every edge-colored graph $G$ with no properly colored $K_{s,t}$ contains a spanning subgraph $H$ which admits an orientation $D$ such that every directed cycle in $D$ is a properly colored cycle in $G$. Using this result, we show that for $rgeq4$, if the Caccetta-H{a}ggkvist Conjecture holds , then every edge-colored graph of order $n$ with minimum color degree at least $n/r+2sqrt{n}+1$ contains a properly colored cycle of length at most $r$. In addition, we also obtain an asymptotically tight total color degree condition which ensures a properly colored (or rainbow) $K_{s,t}$.
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.
It is conjectured that every edge-colored complete graph $G$ on $n$ vertices satisfying $Delta^{mon}(G)leq n-3k+1$ contains $k$ vertex-disjoint properly edge-colored cycles. We confirm this conjecture for $k=2$, prove several additional weaker results for general $k$, and we establish structural properties of possible minimum counterexamples to the conjecture. We also reveal a close relationship between properly edge-colored cycles in edge-colored complete graphs and directed cycles in multi-partite tournaments. Using this relationship and our results on edge-colored complete graphs, we obtain several partial solutions to a conjecture on disjoint cycles in directed graphs due to Bermond and Thomassen.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
