# 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.

[error in script] [error in script]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 |

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. [2] A. Brandstädt, S. Mahfud, Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time, Inform. Process. Lett. 84 (2002) 251–259. [3] P. Damaschke, Induced subgraphs and well-quasi-ordering, J. Graph Theory 14 (1990) 427–435. [4] Guoli Ding, Subgraphs and well-quasi-ordering, J. Graph Theory 16 (1992) 489–502. [5] Guoli Ding, Stable sets versus independent sets, Discrete Math. 117 (1993) 73–87. [6] G. Higman, Ordering by divisibility of abstract algebras, Proc. Lond. Math. Soc. 2 (1952) 326–336. [7] N. Korpelainen, V. Lozin, Bipartite induced subgraphs and well-quasi-ordering, J. Graph Theory (2011) published online, doi:10.1002/jgt.20528. [8] J.B. Kruskal, Well-quasi-ordering, the tree theorem, and Vazsonyi’s conjecture, Trans. Amer. Math. Soc. 95 (1960) 210–225. [9] R. McConnell, J.P. Spinrad, Modular decomposition and transitive orientation, Discrete Math. 201 (1999) 189–241. [10] S. Olariu, Paw-free graphs, Inform. Process. Lett. 28 (1988) 53–54. [11] M. Petkovšek, Letter graphs and well-quasi-order by induced subgraphs, Discrete Math. 244 (2002) 375–388. [12] N. Robertson, P.D. Seymour, Graph Minors. XX. Wagner’s conjecture, J. Combin. Theory Ser. B 92 (2004) 325–357. [13] I.E. Zverovich, A solution to a problem of Jacobson, Kézdy and Lehel, Graphs Combin. 20 (2004) 571–577. |

URI: | http://wrap.warwick.ac.uk/id/eprint/39489 |

Data sourced from Thomson Reuters' Web of Knowledge

### Actions (login required)

View Item |