𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Subgraphs and well-quasi-ordering

✍ Scribed by Guoli Ding

Publisher
John Wiley and Sons
Year
1992
Tongue
English
Weight
712 KB
Volume
16
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let 𝒴 be a class of graphs and let ⪯ be the subgraph or the induced subgraph relation. We call ⪯ an ideal (with respect to ⪯) if ⪯ implies that ⪯. In this paper, we study the ideals that are well‐quasiordered by ⪯. The following are our main results. If ⪯ is the subgraph relation, we characterize the well‐quasi‐ordered ideals in terms of exluding subgraphs. If⪯is the induced subgraph relation, we present three wellquasi‐ordered ideals. We also construct examples to disprove some of the possible generalizations of our results. The connections between some of our results and digraphs are considered in this paper too.

📜 SIMILAR VOLUMES

Induced subgraphs and well-quasi-orderin
Induced subgraphs and well-quasi-ordering
✍ Peter Damaschke 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 428 KB

## Abstract We study classes of finite, simple, undirected graphs that are (1) lower ideals (or hereditary) in the partial order of graphs by the induced subgraph relation ≤~i~, and (2) well‐quasi‐ordered (WQO) by this relation. The main result shows that the class of cographs (__P~4~__‐free graphs

Bipartite induced subgraphs and well-qua
Bipartite induced subgraphs and well-quasi-ordering
✍ Nicholas Korpelainen; Vadim V. Lozin 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 238 KB

We study bipartite graphs partially ordered by the induced subgraph relation. Our goal is to distinguish classes of bipartite graphs that are or are not well-quasi-ordered (wqo) by this relation. Answering an open question from [J Graph Theory 16 (1992), 489-502], we prove that P 7 -free bipartite g

Well Quasi-Ordered Sets
Well Quasi-Ordered Sets
✍ F. Richman; G. Stolzenberg 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 322 KB