Bipartite Graphs Are Not Well-Quasi-Ordered by Bipartite Minors
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914368472481792 |
|---|---|
| author | Biedl, Therese Vitorino, Dinis |
| author_facet | Biedl, Therese Vitorino, Dinis |
| contents | In "Bipartite minors" [Journal of Combinatorial Theory, Series B, 2016], Chudnovsky et al. introduced the bipartite minor relation, a quasi-order on the class of bipartite graphs somewhat analogous the minor relation on general graphs and asked whether it is a well-quasi-order. We answer this question negatively by giving an infinite set of 2-connected bipartite graphs that are pairwise incomparable with respect to the bipartite minor relation. We additionally give two sets of infinitely many pairs of bipartite graphs: one set of pairs G, H such that H is a bipartite minor, but not a minor, of G, and one set of pairs G, H such that H is a minor, but not a bipartite minor, of G. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_23101 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Bipartite Graphs Are Not Well-Quasi-Ordered by Bipartite Minors Biedl, Therese Vitorino, Dinis Combinatorics 05C83 In "Bipartite minors" [Journal of Combinatorial Theory, Series B, 2016], Chudnovsky et al. introduced the bipartite minor relation, a quasi-order on the class of bipartite graphs somewhat analogous the minor relation on general graphs and asked whether it is a well-quasi-order. We answer this question negatively by giving an infinite set of 2-connected bipartite graphs that are pairwise incomparable with respect to the bipartite minor relation. We additionally give two sets of infinitely many pairs of bipartite graphs: one set of pairs G, H such that H is a bipartite minor, but not a minor, of G, and one set of pairs G, H such that H is a minor, but not a bipartite minor, of G. |
| title | Bipartite Graphs Are Not Well-Quasi-Ordered by Bipartite Minors |
| topic | Combinatorics 05C83 |
| url | https://arxiv.org/abs/2601.23101 |