References & Citations
Mathematics > Combinatorics
Title: Rainbow Hamiltonicity in uniformly coloured perturbed graphs
(Submitted on 18 Apr 2023 (v1), revised 27 Oct 2023 (this version, v2), latest version 27 Mar 2024 (v3))
Abstract: We investigate the existence of a rainbow Hamilton cycle in a uniformly edge-coloured randomly perturbed graph. We show that for every $\delta \in (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 $\delta n$ 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 \cup G(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.
Submission history
From: Kyriakos Katsamaktsis [view email][v1] Tue, 18 Apr 2023 17:49:57 GMT (136kb,D)
[v2] Fri, 27 Oct 2023 17:05:31 GMT (462kb,D)
[v3] Wed, 27 Mar 2024 12:31:01 GMT (184kb,D)
Link back to: arXiv, form interface, contact.