Packing Hamilton Cycles Online. (22nd March 2018)

• Record Type: Journal Article
• Authors: BRIGGS, JOSEPH; FRIEZE, ALAN; KRIVELEVICH, MICHAEL; LOH, PO-SHEN; SUDAKOV, BENNY
• Is Part Of: Combinatorics, probability and computing. Volume 27:Number 4(2018)
• Page Start: 475
• Page End: 495
• Publication Date: 2018-03-22
• Subjects: Primary 05C80, -- Secondary 05C15; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548318000159
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : It is known that w.h.p. the hitting time τ2σ for the random graph process to have minimum degree 2σ coincides with the hitting time for σ edge-disjoint Hamilton cycles [4, 9, 13]. In this paper we prove an online version of this property. We show that, for a fixed integer σ ⩾ 2, if random edges of Kn are presented one by one then w.h.p. it is possible to colour the edges online with σ colours so that at time τ2σ each colour class is Hamiltonian.