Rainbow Hamiltonicity in uniformly coloured perturbed digraphs

arXiv2304.09155MaRDI QIDQ6509704FDOQ6509704

Authors: Kyriakos Katsamaktsis, Shoham Letzter 

Abstract: We investigate the existence of a rainbow Hamilton cycle in a uniformly edge-coloured randomly perturbed graph. We show that for every $deltain(0,1)$ there exists $C=C(delta)>0$ such that the following holds. Let $G_0$ be an $n$-vertex graph with minimum degree at least $deltan$ and suppose that each edge of the union of $G_0$, with the random graph $G(n,p)$ on the same vertex set, gets a colour in $[n]$ independently and uniformly at random. Then, with high probability, $G_{0}cupG(n,p)$ has a rainbow Hamilton cycle. This improves a result of Aigner-Horev and Hefetz, who proved the same when the edges are coloured uniformly in a set of $(1+epsilon)n$ colours.

This page was built for publication: Rainbow Hamiltonicity in uniformly coloured perturbed digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6509704)