Maurice Pouzet ; Imed Zaguia
-
Graphs containing finite induced paths of unbounded length
dmtcs:6915 -
Discrete Mathematics & Theoretical Computer Science,
March 8, 2022,
vol. 23 no. 2, special issue in honour of Maurice Pouzet
-
https://doi.org/10.46298/dmtcs.6915
Graphs containing finite induced paths of unbounded lengthArticle
Authors: Maurice Pouzet ; Imed Zaguia
NULL##NULL
Maurice Pouzet;Imed Zaguia
The age A(G) of a graph G (undirected and without loops) is the
collection of finite induced subgraphs of G, considered up to isomorphy and
ordered by embeddability. It is well-quasi-ordered (wqo) for this order if it
contains no infinite antichain. A graph is \emph{path-minimal} if it contains
finite induced paths of unbounded length and every induced subgraph G′ with
this property embeds G. We construct 2ℵ0 path-minimal graphs whose
ages are pairwise incomparable with set inclusion and which are wqo. Our
construction is based on uniformly recurrent sequences and lexicographical sums
of labelled graphs.