Subgraphs and well‐quasi‐ordering
Author:
- 1 November 1992
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 16 (5) , 489-502
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.Keywords
This publication has 2 references indexed in Scilit:
- Induced subgraphs and well‐quasi‐orderingJournal of Graph Theory, 1990
- Ordering by Divisibility in Abstract AlgebrasProceedings of the London Mathematical Society, 1952