Minimal prime ages, words and permutation graphs
Contributions to Discrete Mathematics · 2026
DOI: 10.55016/hzvb3p31 ↗Kurz gefasst
Fachartikel in der Zeitschrift Contributions to Discrete Mathematics, 2026. Verfasst von Djamila Oudrar und 2 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY-ND 4.0).
Abstract (Originalsprache)
This paper is a contribution to the study of hereditary classes of finite graphs. We classify these classes according to the number of prime structures they contain. We consider such classes that are minimal prime: classes that contain infinitely many primes but every proper hereditary subclass contains only finitely many primes. We give a complete description of such classes. In fact, each one of these classes is a well-quasi-ordered age and there are uncountably many of them. Eleven of these ages are almost multichainable; they remain well-quasi-ordered when labels from a well-quasi-ordering are added, hence have finitely many bounds. Five ages among them are exhaustible. Among the remaining ones, only countably many remain well-quasi-ordered when one label is added, and these have finitely many bounds (except for the age of the infinite path and its complement). The others have infinitely many bounds. Except for six examples, members of these ages we characterize are permutation graphs. In fact, every age which is not among the eleven ones is the age of a graph associated to a uniformly recurrent word on the integers. A description of minimal prime classes of posets and bichains is also provided. Our results hint towards the truth of three conjectures. One stating that if a hereditary class of finite graphs does not remain well-quasi-ordered when adding labels in a well-quasi ordered set to these graphs, then it is not well-quasi-ordered when adding just two constants to each of these graphs.
Zitieren
APA
Oudrar, D., Zaguia, I., & Pouzet, M. (2026). Minimal prime ages, words and permutation graphs. Contributions to Discrete Mathematics. https://doi.org/10.55016/hzvb3p31
Vancouver
Oudrar D, Zaguia I, Pouzet M. Minimal prime ages, words and permutation graphs. Contributions to Discrete Mathematics. 2026. doi:10.55016/hzvb3p31
BibTeX
@article{Oudrar2026,
author = {Oudrar, Djamila and Zaguia, Imed and Pouzet, Maurice},
title = {Minimal prime ages, words and permutation graphs},
journal = {Contributions to Discrete Mathematics},
year = {2026},
doi = {10.55016/hzvb3p31}
}
EUVIMED