| Autor: |
Korpelainen, Nicholas, Lozin, Vadim V. |
| Rok vydání: |
2010 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
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. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
