1 results
Rainbow Hamiltonicity in uniformly coloured perturbed digraphs
- Part of
-
- Journal:
- Combinatorics, Probability and Computing / Volume 33 / Issue 5 / September 2024
- Published online by Cambridge University Press:
- 13 May 2024, pp. 624-642
-
- Article
-
- You have access
- Open access
- HTML
- Export citation
-
We investigate the existence of a rainbow Hamilton cycle in a uniformly edge-coloured randomly perturbed digraph. We show that for every
$\delta \in (0,1)$ there exists 
$C = C(\delta ) \gt 0$ such that the following holds. Let 
$D_0$ be an 
$n$-vertex digraph with minimum semidegree at least 
$\delta n$ and suppose that each edge of the union of 
$D_0$ with a copy of the random digraph 
$\mathbf{D}(n,C/n)$ on the same vertex set gets a colour in 
$[n]$ independently and uniformly at random. Then, with high probability, 
$D_0 \cup \mathbf{D}(n,C/n)$ has a rainbow directed Hamilton cycle.This improves a result of Aigner-Horev and Hefetz ((2021) SIAM J. Discrete Math. 35(3) 1569–1577), who proved the same in the undirected setting when the edges are coloured uniformly in a set of
$(1 + \varepsilon )n$ colours.
