Two forbidden induced subgraphs and well-quasi-ordering

Korpelainen, Nicholas and Lozin, Vadim (2011). Two forbidden induced subgraphs and well-quasi-ordering. Discrete Mathematics, 311(16) pp. 1813–1822.

DOI: https://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₄. 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.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 38891
• Item Type
• Journal Item
• ISSN
• 1872-681X
• Keywords
• induced subgraph relation; well-quasi-order; antichain
• Academic Unit or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Copyright Holders
• © 2011 Elsevier B.V.
• Depositing User
• Nicholas Korpelainen