Transversal Hamilton Paths and Cycles

Abstract. Given a collection [Formula: see text] of graphs on the common vertex set [Formula: see text] of size [Formula: see text], an [Formula: see text]-edge graph [Formula: see text] with vertices in [Formula: see text] is a transversal in [Formula: see text] if there exists a bijection [Formula: see text] such that [Formula: see text] for all [Formula: see text]. Denote [Formula: see text]. In this paper, we first establish a minimum degree condition for the existence of transversal Hamilton paths in [Formula: see text]: if [Formula: see text] and [Formula: see text], then [Formula: see text] contains a transversal Hamilton path. This solves a problem proposed by [L. Li, P. Li, and X. Li, J. Graph Theory, 104 (2023), pp. 341–359]. As a continuation of the transversal version of Dirac’s theorem [F. Joos and J. Kim, Bull. Lond. Math. Soc., 52 (2020), 498–504] and the stability result for transversal Hamilton cycles [Y. Cheng and K. Staden, Electron. J. Combin., 32 (2025), P4.36], our second result characterizes all graph collections with minimum degree at least [Formula: see text] and without transversal Hamilton cycles. We obtain an analogous result for transversal Hamilton paths. The proof is a combination of the stability result for transversal Hamilton paths and cycles and the transversal blow-up lemma, along with some structural analysis.