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.



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


Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions
No digital document available to download for this item

Item Actions