Article ID Journal Published Year Pages File Type
4648651 Discrete Mathematics 2011 10 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,