Two forbidden induced subgraphs and well-quasi-ordering
Two forbidden induced subgraphs and well-quasi-ordering
复制标题
两个禁止诱导子图和良好准序
DOI：
10.1016/j.disc.2011.04.023
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
V. Lozin
中科院分区：
文献类型：
--
作者：
N. Korpelainen;V. Lozin
已知由一个禁止导出子图G定义的一类图是由导出子图关系良准序的当且仅当G是P4的导出子图.然而，很少有人知道的好准有序类的图定义了一个以上的禁止诱导子图。我们猜想，对于任意自然数k，存在n个由k个禁止导出子图定义的极小图类，这些图类不是由导出子图关系所定义的良好拟序图，并证明了k= 2时的猜想.我们明确揭示了许多最小类定义的两个禁止诱导子图是不好的准序和许多那些是好的准序的诱导子图关系。
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.