Back to Search
Start Over
Two forbidden induced subgraphs and well-quasi-ordering
- Source :
-
Discrete Mathematics . Aug2011, Vol. 311 Issue 16, p1813-1822. 10p. - Publication Year :
- 2011
-
Abstract
- Abstract: It is known that a class of graphs defined by a single forbidden induced subgraph is well-quasi-ordered by the induced subgraph relation if and only if is an induced subgraph of . 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 , there are finitely many minimal classes of graphs defined by forbidden induced subgraphs which are not well-quasi-ordered by the induced subgraph relation and prove the conjecture for . 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. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 311
- Issue :
- 16
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 60925938
- Full Text :
- https://doi.org/10.1016/j.disc.2011.04.023