𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Bipartite induced subgraphs and well-quasi-ordering

✍ Scribed by Nicholas Korpelainen; Vadim V. Lozin

Publisher
John Wiley and Sons
Year
2011
Tongue
English
Weight
238 KB
Volume
67
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 graphs are not wqo. On the other hand, we show that P 6 -free bipartite graphs are wqo. We also obtain some partial results on subclasses of bipartite graphs defined by forbidding more than one induced subgraph.

πŸ“œ 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