Rainbow Hamiltonian cycles in strongly edge-colored graphs

Abstract The classical Dirac’s theorem states that every graph G with order at least 3 and minimum degree δ ( G ) ≥ | G | 2 contains a Hamiltonian cycle. Let G be an edge-colored graph. A subgraph of an edge-colored graph is called rainbow if all its edges have different colors. In 1980 Hahn conjectured that every properly edge-colored complete graph K n has a rainbow Hamiltonian path. Although this conjecture turns out to be false, it is widely believed that such a coloring always contains a rainbow cycle of length at least n − 2 . Inspired by this conjecture, we consider the existence of rainbow Hamiltonian cycles in strongly edge-colored graphs. A strongly edge-colored graph is an edge-colored graph such that every path of length 3 is rainbow, namely, every monochromatic subgraph is an induced matching. We prove that every strongly edge-colored graph G with minimum degree δ ( G ) ≥ 2 | G | 3 contains a rainbow Hamiltonian cycle. We also prove that every strongly edge-colored graph G with minimum degree δ ( G ) ≥ | G | 2 contains a rainbow spanning tree.