Colorful Hamilton cycles in random graphs

Debsoumya Chakraborti; Alan Frieze; Mihir Hasabnis

doi:10.1137/21M1403291

paper

Colorful Hamilton cycles in random graphs

arXiv:2103.03916 · doi:10.1137/21M1403291

Abstract

Given an $n$ vertex graph whose edges have colored from one of $r$ colors $C = {c_{1}, c_{2}, \dots, c_{r}}$ , we define the Hamilton cycle color profile $h c p (G)$ to be the set of vectors $(m_{1}, m_{2}, \dots, m_{r}) \in [0, n]^{r}$ such that there exists a Hamilton cycle that is the concatenation of $r$ paths $P_{1}, P_{2}, \dots, P_{r}$ , where $P_{i}$ contains $m_{i}$ edges of color $c_{i}$ . We study $h c p (G_{n, p})$ when the edges are randomly colored. We discuss the profile close to the threshold for the existence of a Hamilton cycle and the threshold for when $h c p (G_{n, p}) = {(m_{1}, m_{2}, \dots, m_{r}) \in [0, n]^{r} : m_{1} + m_{2} + \dots + m_{r} = n}$ .

fixed minor typos