Well-quasi-ordering of combinatorial structures
Aistis Atminas · Warwick Research Archive Portal (University of Warwick) · 2015
In this work we study the notion of well-quasi-ordering for various partial orders and its relation to some other notions, such as clique-width. In particular, we prove decidability of well-quasi-ordering for factorial languages, subquadratic properties of graphs and classes of graphs with finite distinguishing number. In addition, we reveal some new classes of graphs and permutations which are or are not well-quasi-ordered. We also prove that subquadratic properties or classes of graphs with finite distinguishing number that are well-quasi-ordered have bounded clique-width and we identify two new minimal classes of graphs of unbounded clique-width.