Copy the page URI to the clipboard
Korpelainen, Nicholas and Lozin, Vadim V.
(2011).
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 P7-free bipartite graphs are not wqo. On the other hand, we show that P6-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
Public Attention
Altmetrics from AltmetricNumber of Citations
Citations from DimensionsItem Actions
Export
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