The Library
Two forbidden induced subgraphs and well-quasi-ordering
Tools
Korpelainen, Nicholas and Lozin, Vadim V. (2011) Two forbidden induced subgraphs and well-quasi-ordering. Discrete Mathematics & Theoretical Computer Science, Vol.311 (No.16). pp. 1813-1822. doi:10.1016/j.disc.2011.04.023 ISSN 1365-8050.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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 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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > 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: | 1365-8050 | ||||
Official Date: | 2011 | ||||
Dates: |
|
||||
Volume: | Vol.311 | ||||
Number: | No.16 | ||||
Page Range: | pp. 1813-1822 | ||||
DOI: | 10.1016/j.disc.2011.04.023 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |