Some algorithmic results on Hamiltonicity and its variants in \(P_6\)-free graphs (Q2093879)

This paper investigates the structure of \(P_6\)-free chordal bipartite graphs and gives a polynomial-time algorithm for finding a Hamiltonian cycle. This problem is known to be NP-hard for general chordal bipartite graphs. The paper even gives polynomial-time algorithms for the Hamiltonian path, longest path, and longest cycle in this graph subclass. The authors also extend known results for the \(P_5\)-free chordal bipartite graphs by showing that the feedback vertex set, vertex cover, and clique cover are polynomial for \(P_5\)-free chordal bipartite graphs.