Title: Infinitely many minimal classes of graphs of unbounded clique-width,
Abstract: The celebrated theorem of Robertson and Seymour states that in the family of
minor-closed graph classes, there is a unique minimal class of graphs of
unbounded tree-width, namely, the class of planar graphs. In the case of
tree-width, the restriction to minor-closed classes is justified by the fact
that the tree-width of a graph is never smaller than the tree-width of any of
its minors. This, however, is not the case with respect to clique-width, as the
clique-width of a graph can be (much) smaller than the clique-width of its
minor. On the other hand, the clique-width of a graph is never smaller than the
clique-width of any of its induced subgraphs, which allows us to be restricted
to hereditary classes (that is, classes closed under taking induced subgraphs),
when we study clique-width. Up to date, only finitely many minimal hereditary
classes of graphs of unbounded clique-width have been discovered in the
literature. In the present paper, we prove that the family of such classes is
infinite. Moreover, we show that the same is true with respect to linear
clique-width.