Labelled Well Quasi Ordered Classes of Bounded Linear Clique-Width
<|reference_start|>Labelled Well Quasi Ordered Classes of Bounded Linear Clique-Width: 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\'e, by uncovering a connection between well-quasi-orderings on graphs and the gap embedding relation of Dershowitz and Tzameret.<|reference_end|>
@article{lopez2024labelled,
    title={Labelled Well Quasi Ordered Classes of Bounded Linear Clique-Width},
    author={Aliaume Lopez},
    journal={arXiv preprint arXiv:2405.10894},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.10894},
    primaryClass={cs.LO}
}