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