Edge-disjoint Hamilton cycles under a bipartite-hole condition

Abstract

In 2017, McDiarmid and Yolov introduced the bipartite-hole-number $\tilde{\alpha }(G)$ and proved that $\delta (G)\ge \tilde{\alpha }(G)$ forces a Hamilton cycle. They also gave a sufficient condition for packing edge-disjoint Hamilton cycles, and asked whether this condition is sharp or can be relaxed. For integers $a,k\ge 2$, let $f(a,k)$ be the least integer $d$ such that every graph $G$ on at least three vertices with $\tilde{\alpha }(G)\le a$ and $\delta (G)\ge d$ contains $k$ pairwise edge-disjoint Hamilton cycles. We prove that $f(a,k)=\Theta \left(a+k+\frac{ak}{\log (k+2)}\right).$ The upper bound uses a deletion lemma for the bipartite-hole-number together with the McDiarmid--Yolov Hamiltonicity theorem and a greedy packing argument. The lower bound is obtained from three extremal constructions, the logarithmic one using a sparse random auxiliary graph with no prescribed bipartite hole.