Well-quasi-ordered classes of bounded clique-width
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911725747437568 |
|---|---|
| author | Dumas, Maël Lopez, Aliaume |
| author_facet | Dumas, Maël Lopez, Aliaume |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_18571 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Well-quasi-ordered classes of bounded clique-width Dumas, Maël Lopez, Aliaume Combinatorics Formal Languages and Automata Theory Logic in Computer Science 05Cxx, 68Q45 G.2.2; F.4.3 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. |
| title | Well-quasi-ordered classes of bounded clique-width |
| topic | Combinatorics Formal Languages and Automata Theory Logic in Computer Science 05Cxx, 68Q45 G.2.2; F.4.3 |
| url | https://arxiv.org/abs/2601.18571 |