The Library
Boundary properties of well-quasi-ordered sets of graphs
Tools
Korpelainen, Nicholas, Lozin, Vadim V. and Razgon, Igor (2013) Boundary properties of well-quasi-ordered sets of graphs. Order, Volume 30 (Number 3). pp. 723-735. doi:10.1007/s11083-012-9272-2 ISSN 0167-8094.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.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 well-quasi-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.
V.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Order | ||||
Publisher: | Springer | ||||
ISSN: | 0167-8094 | ||||
Official Date: | 1 November 2013 | ||||
Dates: |
|
||||
Volume: | Volume 30 | ||||
Number: | Number 3 | ||||
Page Range: | pp. 723-735 | ||||
DOI: | 10.1007/s11083-012-9272-2 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |