Abstract
Let \({\cal 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 \({\cal Y}_2\) 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 \({\cal Y}_2\) 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 \({\cal 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 \({\cal Y}_k\) is wqo or not.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alekseev, V.E.: On easy and hard hereditary classes of graphs with respect to the independent set problem. Discrete Appl. Math. 132, 17–26 (2003)
Alekseev, V.E., Korobitsyn, D.V., Lozin, V.V.: Boundary classes of graphs for the dominating set problem. Discrete Math. 285, 1–6 (2004)
Alekseev, V.E., Boliac, R., Korobitsyn, D.V., Lozin, V.V.: NP-hard graph problems and boundary classes of graphs. Theor. Comput. Sci. 389, 219–236 (2007)
Atkinson, M.D., Murphy, M.M., Ruškuc, N.: Partially well-ordered closed sets of permutations. Order 19, 101–113 (2002)
Brignall, R.: Grid classes and partial well order. J. Comb. Theory Ser. A 119, 99–116 (2012)
Brignall, R., Ruškuc, N., Vatter, V.: Simple permutations: decidability and unavoidable substructures. Theor. Comp. Sci. 391, 150–163 (2008)
Cherlin, G.: Forbidden substructures and combinatorial dichotomies: WQO and universality. Discrete Math. 311, 1543–1584 (2011)
Damaschke, P.: Induced subgraphs and well-quasi-ordering. J. Graph Theory 14, 427–435 (1990)
Ding, G.: Subgraphs and well-quasi-ordering. J. Graph Theory 16, 489–502 (1992)
Higman, G.: Ordering by divisibility of abstract algebras. Proc. Lond. Math. Soc. 2, 326–336 (1952)
Korpelainen, N., Lozin, V.V.: Two forbidden induced subgraphs and well-quasi-ordering. Discrete Math. 311, 1813–1822 (2011)
Korpelainen, N., Lozin, V.V., Malyshev, D.S., Tiskin, A.: Boundary properties of graphs for algorithmic graph problems. Theor. Comp. Sci. 412, 3545–3554 (2011)
Lozin, V.V.: Boundary classes of planar graphs. Comb. Probab. Comput. 17, 287–295 (2008)
Murphy, M.N., Vatter, V.: Profile classes and partial well-order for permutations. Electron. J. Comb. 9(2), #R17 (2003)
Robertson, N., Seymour, P.D.: Graph Minors. XX. Wagner’s conjecture. J. Comb. Theory, Ser. B 92, 325–357 (2004)
Vatter, V., Waton, S.: On partial well-order for monotone grid classes of permutations. Order 28, 193–199 (2011)
Zverovich, I.E.: r-Bounded k-complete bipartite bihypergraphs and generalized split graphs. Discrete Math. 247, 261–270 (2002)
Author information
Authors and Affiliations
Corresponding author
Additional information
V.V. Lozin gratefully acknowledges support from DIMAP—the Center for Discrete Mathematics and its Applications at the University of Warwick, and from EPSRC, grant EP/I01795X/1.
Rights and permissions
About this article
Cite this article
Korpelainen, N., Lozin, V.V. & Razgon, I. Boundary Properties of Well-Quasi-Ordered Sets of Graphs. Order 30, 723–735 (2013). https://doi.org/10.1007/s11083-012-9272-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-012-9272-2