The Hamiltonian Cycle Problem and Monotone Classes

We study the computational complexity of the Hamiltonian cycle problem on monotone classes of graphs, i.e. classes closed under taking subgraphs. We focus on classes defined by a single forbidden subgraph and present some necessary and some sufficient conditions for polynomial-time solvability of the problem in this case (assuming \(P\ne NP\) ). The main result is a polynomial-time algorithm to solve the problem for graphs excluding a certain tree, called the long-H, as a subgraph.