Hamiltonian path and Hamiltonian cycle are solvable in polynomial time in graphs of bounded independence number

Nikola Jedličková, Jan Kratochvíl

A Hamiltonian path (a Hamiltonian cycle) in a graph is a path (a cycle, respectively) that traverses all of its vertices. The problems of deciding their existence in an input graph…