Bipartite Induced Subgraphs and Well-Quasi-Ordering
classification
🧮 math.CO
keywords
bipartitegraphsinducedfreerelationsubgraphansweringcite
read the original abstract
We study bipartite graphs partially ordered by the induced subgraph relation. Our goal is to distinguish classes of bipartite graphs which are or are not well-quasi-ordered (wqo) by this relation. Answering an open question from \cite{Ding92}, we prove that $P_7$-free bipartite graphs are not wqo. On the other hand, we show that $P_6$-free bipartite graphs are wqo. We also obtain some partial results on subclasses of bipartite graphs defined by forbidding more than one induced subgraph.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.