4 papers
Well-quasi-ordered classes of bounded clique-width
Maël Dumas, Aliaume Lopez
We study classes of graphs with bounded clique-width that are well-quasi-ordered by the induced subgraph relation, in the presence of labels on the vertices. We prove that, given a…
Well-Quasi-Orderings on Word Languages
Nathan Lhote, Aliaume Lopez, Lia Schütze
The set of finite words over a well-quasi-ordered set is itself well-quasi-ordered. This seminal result by Higman is a cornerstone of the theory of well-quasi-orderings and has fou…
Measuring well quasi-ordered finitary powersets
Sergio Abriola, Simon Halfon, Aliaume Lopez +3
The complexity of a well-quasi-order (wqo) can be measured through three ordinal invariants: the width as a measure of antichains, height as a measure of chains, and maximal order…
Labelled Well Quasi Ordered Classes of Bounded Linear Clique-Width
Aliaume Lopez
We are interested in characterizing which classes of finite graphs are well-quasi-ordered by the induced subgraph relation. To that end, we devise an algorithm to decide whether a…