Boundary properties of well-quasi-ordered sets of graphs

Korpelainen, Nicholas; Lozin, Vadim V. and Razgon, Igor (2013). Boundary properties of well-quasi-ordered sets of graphs. Order, 30(3) pp. 723–735.

DOI: https://doi.org/10.1007/s11083-012-9272-2

Abstract

Let Yk be the family of hereditary classes of graphs defined by k forbidden induced subgraphs. In Korpelainen and Lozin (Discrete Math 311:1813–1822, 2011), it was shown that Y2 contains only finitely many minimal classes that are not wellquasi- ordered (wqo) by the induced subgraph relation. This implies, in particular, that the problem of deciding whether a class from Y2 is wqo or not admits an efficient solution. Unfortunately, this idea does not work for k ≥ 3, as we show in the present paper. To overcome this difficulty, we introduce the notion of boundary properties of well-quasi-ordered sets of graphs. The importance of this notion is due to the fact that for each k, a class from Yk is wqo if and only if it contains none of the boundary properties. We show that the number of boundary properties is generally infinite. On the other hand, we prove that for each fixed k, there is a finite collection of boundary properties that allow to determine whether a class from Yk is wqo or not.

Viewing alternatives

Metrics

Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions

Export

About

Recommendations