Daligault, Rao and Thomasse proposed in 2010 a fascinating conjecture connecting two seem- ingly unrelated notions: clique-width and well-quasi-ord ering. They asked if the clique-width of graphs in a hereditary class which is well-quasi-ordered under labelled induced subgraphs is bounded by a constant. This is equivalent to asking whether every hereditary class of unbounded clique-width has a labelled infinite antichain. We believe the answer to th is question is positive and propose a stronger conjecture stating that every minimal hereditary class of graphs of unbounded clique-width has a canonical labelled infinite antichain. To date, only two hereditary cl asses are known to be minimal with respect to clique-width and each of them is known to contain a canonical antichain. In the present paper, we discover two more minimal hereditary classes of unbounded clique-width and show that both of them contain canonical antichains.
['Aistis Atminas', 'Robert Brignall', 'Vadim V. Lozin', 'Juraj Stacho']
Minimal Classes of Graphs of Unbounded Clique-width and Well-quasi-ordering