Bipartite minors

详细信息    查看全文

• 作者：Maria Chudnovsky^a ; ^{mchudnov@math.princeton.edu" class="auth_mail" title="E-mail the corresponding author} ; Gil Kalai^b ; ^c ; ^{kalai@math.huji.ac.il" class="auth_mail" title="E-mail the corresponding author} ; Eran Nevo^b ; ^d ; ^{nevo@math.huji.il" class="auth_mail" title="E-mail the corresponding author} ; Isabella Novik^e ; ^{novik@math.washington.edu" class="auth_mail" title="E-mail the corresponding author} ; Paul Seymour^a ; ^{pds@math.princeton.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Minors ; Bipartite graphs ; Bipartite minors ; Kuratowski's theorem ; Laman graphs ; Planar and outerplanar graphs ; Peripheral cycles
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：116
• 期：Complete
• 页码：219-228
• 全文大小：291 K

文摘

We introduce a notion of bipartite minors and prove a bipartite analog of Wagner's theorem: a bipartite graph is planar if and only if it does not contain K_3,3$K_{3,3}$ as a bipartite minor. Similarly, we provide a forbidden minor characterization for outerplanar graphs and forests. We then establish a recursive characterization of bipartite (2,2)$(2,2)$-Laman graphs — a certain family of graphs that contains all maximal bipartite planar graphs.