Vadim Lozin, Graph problems and monotone classes

Very little is known about critical properties of graphs in the hierarchy of monotone classes, i.e. classes closed under taking (not necessarily induced) subgraphs. We distinguish four important levels in this hierarchy and discuss possible new levels by focusing on the Hamiltonian cycle problem. In particular, we obtain a number of results for this problem on monotone classes.