首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Two forbidden induced subgraphs and well-quasi-ordering
Authors:Nicholas Korpelainen  Vadim Lozin
Institution:aDIMAP, University of Warwick, Coventry CV4 7AL, UK
Abstract: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 P4. 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.
Keywords:Induced subgraph relation  Well-quasi-order  Antichain
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号