# 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.
ISSN 1365-8050

**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 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 > 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 |

Volume: | Vol.311 |

Number: | No.16 |

Page Range: | pp. 1813-1822 |

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 |