The Library
Two forbidden induced subgraphs and wellquasiordering
Tools
Korpelainen, Nicholas and Lozin, Vadim V.. (2011) Two forbidden induced subgraphs and wellquasiordering. Discrete Mathematics & Theoretical Computer Science, Vol.311 (No.16). pp. 18131822. ISSN 13658050
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1016/j.disc.2011.04.023
Abstract
It is known that a class of graphs defined by a single forbidden induced subgraph G is wellquasiordered by the induced subgraph relation if and only if G is an induced subgraph of P(4). However, very little is known about wellquasiordered 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 wellquasiordered 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 wellquasiordered and many of those which are wellquasiordered by the induced subgraph relation.
Item Type:  Journal Article  

Subjects:  Q Science > QA Mathematics  
Divisions:  Faculty of Science > Mathematics  
Library of Congress Subject Headings (LCSH):  Graph theory  
Journal or Publication Title:  Discrete Mathematics & Theoretical Computer Science  
Publisher:  D M T C S  
ISSN:  13658050  
Official Date:  2011  
Dates: 


Volume:  Vol.311  
Number:  No.16  
Page Range:  pp. 18131822  
Identification Number:  10.1016/j.disc.2011.04.023  
Status:  Peer Reviewed  
Publication Status:  Published  
References:  [1] A. Brandstädt, (P5, diamond)free graphs revisited: structure and linear time optimization, Discrete Appl. Math. 138 (2004) 13–27. 

URI:  http://wrap.warwick.ac.uk/id/eprint/39489 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Actions (login required)
View Item 