کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648651 | 1342422 | 2011 | 10 صفحه PDF | دانلود رایگان |
It is known that a class of graphs defined by a single forbidden induced subgraph GG is well-quasi-ordered by the induced subgraph relation if and only if GG is an induced subgraph of P4P4. 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 kk, there are finitely many minimal classes of graphs defined by kk forbidden induced subgraphs which are not well-quasi-ordered by the induced subgraph relation and prove the conjecture for k=2k=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.
Journal: Discrete Mathematics - Volume 311, Issue 16, 28 August 2011, Pages 1813–1822