Back to Search Start Over

Rainbow Hamiltonicity in uniformly coloured perturbed digraphs

Authors :
Katsamaktsis, Kyriakos
Letzter, Shoham
Sgueglia, Amedeo
Publication Year :
2023

Abstract

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) > 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 the random digraph $D(n, p)$ on the same vertex set gets a colour in $[n]$ independently and uniformly at random. Then, with high probability, $D_0 \cup D(n, p)$ has a rainbow directed Hamilton cycle. This improves a result of Aigner-Horev and Hefetz (2021) who proved the same in the undirected setting when the edges are coloured uniformly in a set of $(1 + \varepsilon)n$ colours.<br />Comment: Incorporated referee's comments. Accepted for publication in Combinatorics, Probability and Computing

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2304.09155
Document Type :
Working Paper
Full Text :
https://doi.org/10.1017/S0963548324000130