Paper: Well-Quasi-Ordered Classes of Bounded Clique-Width (at LICS 2026)

Authors: Maël Dumas Aliaume Lopez

Open access: https://doi.org/10.4230/LIPIcs.LICS.2026.38

Abstract

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 finite presentation of a class of graphs, one can decide whether the class is labelled-well-quasi-ordered. This answers positively to two conjectures of Pouzet in the restricted case of bounded clique-width classes. Namely, we prove that being labelled-well-quasi-ordered by a set of size 2 or by a well-quasi-ordered infinite set are equivalent conditions, and that in such cases, one can freely assume that the graphs are equipped with a total ordering on their vertices. Finally, we provide a structural characterization of those classes as those that are of bounded clique-width and do not existentially transduce the class of all finite paths.

BibTeX

  @InProceedings{DumasLopez-WellQuasiOrderedCla,
    author = 	 {Maël Dumas and Aliaume Lopez},
    title = 	 {Well-Quasi-Ordered Classes of Bounded Clique-Width},
    booktitle =  {Proceedings of the Forty-First Annual Symposium on Logic in Computer Science (LICS 2026)},
    year =	 {2026},
    month =	 {July}, 
    pages =      {38:1--38:24},
    location =   {Lisbon, Portugal}, 
    publisher =	 {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
    doi =        {10.4230/LIPIcs.LICS.2026.38}
  }