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|
 A. Brandstädt, (P5, diamond)-free graphs revisited: structure and linear time optimization, Discrete Appl. Math. 138 (2004) 13–27.
Actions (login required)
Downloads per month over past year