Packing Hamilton Cycles Online

Abstract

It is known that w.h.p. the hitting time $\ddot{I}{„}_{2\ddot{I}ƒ}$ for the random graph process to have minimum degree $2\ddot{I}ƒ$ coincides with the hitting time for $\ddot{I}ƒ$ edge disjoint Hamilton cycles. In this paper we prove an online version of this property. We show that, for a fixed integer $\ddot{I}ƒ\ge 2$, if random edges of $K_n$ are presented one by one then w.h.p. it is possible to color the edges online with $\ddot{I}ƒ$ colors so that at time $\ddot{I}{„}_{2\ddot{I}ƒ}$, each color class is Hamiltonian.

Minor changes