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 Y_k 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 Y₂ 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 Y₂ 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 Y_k 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 Y_k is wqo or not.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 38893
• Item Type
• Journal Item
• ISSN
• 1572-9273
• Keywords
• well-quasi-order; induced subgraphs
• Academic Unit or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Copyright Holders
• © 2012 Springer Science+Business Media B.V.
• Depositing User
• Nicholas Korpelainen