Two forbidden induced subgraphs and well-quasi-ordering

作者：Korpelainen Nicholas^*; Lozin Vadim

来源：Discrete Mathematics, 2011, 311(16): 1813-1822.

DOI：10.1016/j.disc.2011.04.023

• Induced subgraph relation
• Well-quasi-order
• Antichain

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.

• 出版日期2011-8-28