View article

Given an -vertex graph with minimum degree at least for some fixed , the distribution over the supergraphs of is referred to as a (random) perturbation of . We consider the distribution of edge-colored graphs arising from assigning each edge of the random perturbation a color, chosen independently and uniformly at random from a set of colors of size . We prove that edge-colored graphs which are generated in this manner asymptotically almost surely admit rainbow Hamilton cycles whenever the edge-density of the random perturbation satisfies for some fixed and . The number of colors used is clearly asymptotically best possible. In particular, this improves on a recent result of Anastos and Frieze [J. Graph Theory, 92 (2019), pp. 405--414] in this regard. As an intermediate result, which may be of independent interest, we prove that …