Bipartite induced subgraphs and well-quasi-ordering

Korpelainen, Nicholas and Lozin, Vadim V. (2011). Bipartite induced subgraphs and well-quasi-ordering. Journal of Graph Theory, 67(3) pp. 235–249.

DOI: https://doi.org/10.1002/jgt.20528

Abstract

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

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 38890
• Item Type
• Journal Item
• ISSN
• 1097-0118
• Keywords
• bipartite graph; induced subgraph; well-quasi-ordering
• Academic Unit or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Copyright Holders
• © 2011 Wiley Periodicals, Inc.
• Depositing User
• Nicholas Korpelainen