Bipartite induced subgraphs and well-quasi-ordering
Nicholas Korpelainen, Vadim Lozin · Journal of Graph Theory · 2011
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. Copyright © 2011 John Wiley Periodicals, Inc. J Graph Theory 67: 235-249, 2011