Graph problems and monotone classes

We study properties of graph classes that are closed under taking subclasses, such as boundedness of graph parameters or polynomial-time solvability of algorithmic problems. In the universe of minor-closed classes of graphs, any such property can be described by a set of minimal classes that do not possess the property, because the minor relation is a well-quasi-order. This, however, is not the case for the subgraph relation, implying that in the universe of monotone classes, which extends the family of minor-closed classes, the existence of minimal classes is not guaranteed. To overcome this difficulty, we employ the notion of boundary classes. Together with minimal classes they play a critical role for classes defined by finitely many forbidden subgraphs. In the present paper, we identify several levels in the hierarchy of monotone classes and describe respective critical classes. In particular, we show that a finitely-defined mono- tone class X has bounded chromatic number, degeneracy, functionality and admits an implicit representation if and only if X excludes a forest. We also show that X has bounded tree-, clique- and twin-width and admits polynomial-time solutions for a variety of algorithmic problems if and only if X excludes a tripod, i.e. a subcubic forest every connected component of which has at most one cubic vertex. The last result, however, does not apply to the Hamiltonian cycle problem. Towards identifying critical classes for this problem we determine complexity of the Hamiltonian cycle problem in some monotone classes.