1. COLORFUL HAMILTON CYCLES IN RANDOM GRAPHS.
- Author
-
CHAKRABORT, DEBSOUMYA, FRIEZE, ALAN M., and HASABNIS, MIHIR
- Subjects
- *
RANDOM graphs , *HAMILTONIAN graph theory , *PATHS & cycles in graph theory , *GRAPH coloring - Abstract
Given an n vertex graph whose edges have colored from one of τ colors C = {ci, C2,..., cr}, we define the Hamilton cycle color profile hcp(G) to be the set of vectors (mi, m2,..., mr) ∈ [0, n}r such that there exists a Hamilton cycle that is the concatenation of τ paths Pi, P2, ∙.., Pr, where Pi contains rΠι edges of color cι. 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 ∕icp(Gnjf>) = {(mι, m2,..., mr) ∈ [0,n]r: mi + m2 + ∙ ∙ ∙ + mr = n}. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF