Two forbidden induced subgraphs and well-quasi-ordering
Korpelainen, Nicholas and Lozin, Vadim V.. (2011) Two forbidden induced subgraphs and well-quasi-ordering. Discrete Mathematics & Theoretical Computer Science, Vol.311 (No.16). pp. 1813-1822. ISSN 1365-8050Full text not available from this repository.
Official URL: http://dx.doi.org/10.1016/j.disc.2011.04.023
It is known that a class of graphs defined by a single forbidden induced subgraph G is well-quasi-ordered by the induced subgraph relation if and only if G is an induced subgraph of P(4). However, very little is known about well-quasi-ordered classes of graphs defined by more than one forbidden induced subgraph. We conjecture that for any natural number k, there are finitely many minimal classes of graphs defined by k forbidden induced subgraphs which are not well-quasi-ordered by the induced subgraph relation and prove the conjecture for k = 2. We explicitly reveal many of the minimal classes defined by two forbidden induced subgraphs which are not well-quasi-ordered and many of those which are well-quasi-ordered by the induced subgraph relation.
|Item Type:||Journal Article|
|Subjects:||Q Science > QA Mathematics|
|Divisions:||Faculty of Science > Mathematics|
|Library of Congress Subject Headings (LCSH):||Graph theory|
|Journal or Publication Title:||Discrete Mathematics & Theoretical Computer Science|
|Publisher:||D M T C S|
|Page Range:||pp. 1813-1822|
|References:|| A. Brandstädt, (P5, diamond)-free graphs revisited: structure and linear time optimization, Discrete Appl. Math. 138 (2004) 13–27.  A. Brandstädt, S. Mahfud, Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time, Inform. Process. Lett. 84 (2002) 251–259.  P. Damaschke, Induced subgraphs and well-quasi-ordering, J. Graph Theory 14 (1990) 427–435.  Guoli Ding, Subgraphs and well-quasi-ordering, J. Graph Theory 16 (1992) 489–502.  Guoli Ding, Stable sets versus independent sets, Discrete Math. 117 (1993) 73–87.  G. Higman, Ordering by divisibility of abstract algebras, Proc. Lond. Math. Soc. 2 (1952) 326–336.  N. Korpelainen, V. Lozin, Bipartite induced subgraphs and well-quasi-ordering, J. Graph Theory (2011) published online, doi:10.1002/jgt.20528.  J.B. Kruskal, Well-quasi-ordering, the tree theorem, and Vazsonyi’s conjecture, Trans. Amer. Math. Soc. 95 (1960) 210–225.  R. McConnell, J.P. Spinrad, Modular decomposition and transitive orientation, Discrete Math. 201 (1999) 189–241.  S. Olariu, Paw-free graphs, Inform. Process. Lett. 28 (1988) 53–54.  M. Petkovšek, Letter graphs and well-quasi-order by induced subgraphs, Discrete Math. 244 (2002) 375–388.  N. Robertson, P.D. Seymour, Graph Minors. XX. Wagner’s conjecture, J. Combin. Theory Ser. B 92 (2004) 325–357.  I.E. Zverovich, A solution to a problem of Jacobson, Kézdy and Lehel, Graphs Combin. 20 (2004) 571–577.|
Actions (login required)