✦ LIBER ✦

Induced subgraphs and well-quasi-ordering

✍ Scribed by Peter Damaschke

Publisher: John Wiley and Sons
Year: 1990
Tongue: English
Weight: 428 KB
Volume: 14
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190140406

No coin nor oath required. For personal study only.

✦ Synopsis

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) is WQO by ≤~i~, and that this is the unique maximal lower ideal with one forbidden subgraph that is WQO. This is a consequence of the famous Kruskal theorem. Modifying our idea we can prove that P~4~‐reducible graphs build a WQO class. Other examples of lower ideals WQO by ≤~i~ are also given.

📜 SIMILAR VOLUMES

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

✍ F. Richman; G. Stolzenberg 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 322 KB

Branch-Width and Well-Quasi-Ordering in

Branch-Width and Well-Quasi-Ordering in Matroids and Graphs

✍ James F. Geelen; A.M.H. Gerards; Geoff Whittle 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 172 KB

Component factors and induced subgraphs

✍ Nishimura, Tsuyoshi 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 207 KB

Let G and K be connected graphs such that I GI = nlKl (n 2 2) and let p be a fixed integer satisfying 1 < p < n. We prove that if G \ A has a K-factor for every connected subgraph A with IAl = plKI, then G also has a K-factor.

Line Graphs and Forbidden Induced Subgra

Line Graphs and Forbidden Induced Subgraphs

✍ Hong-Jian Lai; Ľubomı&#x0301;r Šoltés 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 242 KB

Beineke and Robertson independently characterized line graphs in terms of nine forbidden induced subgraphs. In 1994, S8 olte s gave another characterization, which reduces the number of forbidden induced subgraphs to seven, with only five exceptional cases. A graph is said to be a dumbbell if it con

Induced subgraphs of prescribed size

✍ Noga Alon; Michael Krivelevich; Benny Sudakov 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract A subgraph of a graph __G__ is called __trivial__ if it is either a clique or an independent set. Let __q(G)__ denote the maximum number of vertices in a trivial subgraph of __G__. Motivated by an open problem of Erdős and McKay we show that every graph __G__ on __n__ vertices for which