COLORFUL HAMILTON CYCLES IN RANDOM GRAPHS

Abstract

Given an n vertex graph whose edges have colored from one of r colors C = { c1, c2,..., cr}, we define the Hamilton cycle color profile hcp(G) to be the set of vectors (m1, m2,..., mr) in [0, n]r such that there exists a Hamilton cycle that is the concatenation of r paths P1, P2,..., Pr, where Pi contains mi edges of color ci. We study hcp(Gn,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 hcp(Gn,p) = {(m1, m2,..., mr) in [0, n]r : m1 + m2 +... + mr = n}. © 2023 Society for Industrial and Applied Mathematics.