We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Rainbow Hamilton cycles in random geometric graphs.
- Authors
Frieze, Alan; Pérez‐Giménez, Xavier
- Abstract
Let X1,X2,...,Xn$$ {X}_1,{X}_2,\dots, {X}_n $$ be chosen independently and uniformly at random from the unit d$$ d $$‐dimensional cube [0,1]d$$ {\left[0,1\right]}^d $$. Let r$$ r $$ be given and let 풳=X1,X2,...,Xn. The random geometric graph G=G풳,r has vertex set 풳 and an edge XiXj$$ {X}_i{X}_j $$ whenever ‖Xi−Xj‖≤r$$ \left\Vert {X}_i-{X}_j\right\Vert \le r $$. We show that if each edge of G$$ G $$ is colored independently from one of n+o(n)$$ n+o(n) $$ colors and r$$ r $$ has the smallest value such that G$$ G $$ has minimum degree at least two, then G$$ G $$ contains a rainbow Hamilton cycle asymptotically almost surely.
- Subjects
RAMSEY numbers; RANDOM graphs; CUBES
- Publication
Random Structures & Algorithms, 2024, Vol 64, Issue 4, p878
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.21201