A new sufficient condition for the existence of alternating Hamiltonian cycles in 2-edge-colored multigraphs

A path (cycle) in a c-edge-colored multigraph is alternating if no two consecutive edges have the same color. The problem of determining the existence of alternating Hamiltonian paths and cycles in 2-edge-colored multigraphs is NP-complete (Gorbenko and Popov, 2012) and it has been studied by several authors. Given a 2-colored multigraph G, an alternating 3-path P=(x1,x2,x3,x4) is closed-alternating if there exist y, w∈V(G) such that C=(x1,y,w,x4,x1) is an alternating cycle. Furthermore, G is closed-alternating whenever each alternating 3-path is closed-alternating. In this work, we prove that if G is connected, closed-alternating and it has an alternating cycle factor (i.e., a collection of vertex-disjoint alternating cycles that covers all the vertices), then G has an alternating Hamiltonian cycle.