Labelled Well Quasi Ordered Classes of Bounded Linear Clique-Width
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917709097205760 |
|---|---|
| author | Lopez, Aliaume |
| author_facet | Lopez, Aliaume |
| contents | 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 class of finite graphs well-quasi-ordered by the induced subgraph relation when the vertices are labelled using a finite set. In this process, we answer positively to a conjecture of Pouzet, under the extra assumption that the class is of bounded linear clique-width. As a byproduct of our approach, we obtain a new proof of an earlier result from Daliagault, Rao, and Thomassé, by uncovering a connection between well-quasi-orderings on graphs and the gap embedding relation of Dershowitz and Tzameret. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_10894 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Labelled Well Quasi Ordered Classes of Bounded Linear Clique-Width Lopez, Aliaume Logic in Computer Science 68Q45, 03B70, 03D05 F.4.3; F.4.1 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 class of finite graphs well-quasi-ordered by the induced subgraph relation when the vertices are labelled using a finite set. In this process, we answer positively to a conjecture of Pouzet, under the extra assumption that the class is of bounded linear clique-width. As a byproduct of our approach, we obtain a new proof of an earlier result from Daliagault, Rao, and Thomassé, by uncovering a connection between well-quasi-orderings on graphs and the gap embedding relation of Dershowitz and Tzameret. |
| title | Labelled Well Quasi Ordered Classes of Bounded Linear Clique-Width |
| topic | Logic in Computer Science 68Q45, 03B70, 03D05 F.4.3; F.4.1 |
| url | https://arxiv.org/abs/2405.10894 |