Let $G$ be a simple complete graph with an edge-2-coloring. An alternating Hamilton (x,y)-path is a Hamiltonian path which starts at vertex $x$ and ends at vertex $y$ such that the colors of its edges alternate along the path. In [1], J. Bang-Jensen and G. Gutin pose the following problem:

Problem 5.14 Is there a polynomial time algorithm for finding an alternating (x,y)-hamiltonian path in $G$ with $x, y$ given?

Does anyone happen to know the status of this problem? I believe the problem is in P if the endvertices are not specified.

[1] Bang-Jensen, G. and Gutin, G., Alternating cycles and paths in edge-coloured multigraphs: A survey, Discrete Mathematics 165/166 (1997) 39-60



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.