Two forbidden induced subgraphs and well-quasi-ordering

DOI10.1016/j.disc.2011.04.023zbMath1223.05132OpenAlexW2122172628MaRDI QIDQ2275404

Vadim V. Lozin, Nicholas Korpelainen

Publication date: 8 August 2011

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2011.04.023

zbMATH Keywords

antichainwell-quasi-orderinduced subgraph relation

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Related Items (23)

Labelled well-quasi-order for permutation classes ⋮ Word-Representable Graphs: a Survey ⋮ Graph isomorphism for graph classes characterized by two forbidden induced subgraphs ⋮ WQO is decidable for factorial languages ⋮ Boundary properties of well-quasi-ordered sets of graphs ⋮ Labelled induced subgraphs and well-quasi-ordering ⋮ Critical properties of bipartite permutation graphs ⋮ Induced minors and well-quasi-ordering ⋮ Recent Progress on Well-Quasi-ordering Graphs ⋮ Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs ⋮ Well-quasi-ordering versus clique-width ⋮ Well-quasi-ordering versus clique-width: new results on bigenic classes ⋮ Letter graphs and geometric grid classes of permutations: characterization and recognition ⋮ WQO dichotomy for 3-graphs ⋮ Clique-width and well-quasi-ordering of triangle-free graph classes ⋮ Deciding the Bell Number for Hereditary Graph Properties ⋮ Sandwiches missing two ingredients of order four ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes ⋮ Well-quasi-ordering Does Not Imply Bounded Clique-width ⋮ Well-quasi-order for permutation graphs omitting a path and a clique ⋮ Hereditary classes of graphs: a parametric approach ⋮ On well quasi-order of graph classes under homomorphic image orderings

Cites Work

• Stable sets versus independent sets
• A solution to a problem of Jacobson, Kézdy and Lehel
• Graph minors. XX: Wagner's conjecture
• Paw-free graphs
• Modular decomposition and transitive orientation
• Letter graphs and well-quasi-order by induced subgraphs
• (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
• Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
• Bipartite induced subgraphs and well-quasi-ordering
• Subgraphs and well‐quasi‐ordering
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
• Induced subgraphs and well‐quasi‐ordering
• Ordering by Divisibility in Abstract Algebras

This page was built for publication: Two forbidden induced subgraphs and well-quasi-ordering