Bipartite Induced Subgraphs and Well-Quasi-Ordering

Details Bipartite Induced Subgraphs and Well-Quasi-Ordering Bipartite Induced Subgraphs and Well-Quasi-Ordering

2010-05-08

arxiv.org/abs/1005.1328v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Bipartite Induced Subgraphs and Well-Quasi-Ordering does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bipartite Induced Subgraphs and Well-Quasi-Ordering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bipartite Induced Subgraphs and Well-Quasi-Ordering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-303413