Bipartite minors

被引：6

作者：

Chudnovsky, Maria ^{[1
]}

Kalai, Gil ^{[2
,3
,4
]}

Nevo, Eran ^{[2
,5
]}

Novik, Isabella ^{[6
]}

Seymour, Paul ^{[1
]}

机构：

[1] Princeton Univ, Dept Math, Princeton, NJ 08544 USA

[2] Hebrew Univ Jerusalem, Inst Math, IL-91904 Jerusalem, Israel

[3] Yale Univ, Dept Comp Sci, New Haven, CT 06511 USA

[4] Yale Univ, Dept Math, New Haven, CT 06511 USA

[5] Ben Gurion Univ Negev, Dept Math, IL-84105 Beer Sheva, Israel

[6] Univ Washington, Dept Math, Seattle, WA 98195 USA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2016年 / 116卷

基金：

美国国家科学基金会;

关键词：

Minors; Bipartite graphs; Bipartite minors; Kuratowski's theorem; Laman graphs; Planar and outerplanar graphs; Peripheral cycles; GRAPHS;

D O I：

10.1016/j.jctb.2015.08.001

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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,K-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)-Laman graphs a certain family of graphs that contains all maximal bipartite planar graphs. (C) 2015 Elsevier Inc. All rights reserved.

引用

页码：219 / 228

页数：10

共 50 条

[1] Topological minors in bipartite graphs
Camino Balbuena
Martín Cera
Pedro García-Vázquez
Juan Carlos Valenzuela
Acta Mathematica Sinica, English Series, 2011, 27 : 2085 - 2100
[2] Topological Minors in Bipartite Graphs
Balbuena, Camino
Cera, Martin
Garcia-Vazquez, Pedro
Carlos Valenzuela, Juan
ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2011, 27 (11) : 2085 - 2100
[3] A Flat Wall Theorem for Matching Minors in Bipartite Graphs
Giannopoulou, Archontia C.
Wiederrecht, Sebastian
PROCEEDINGS OF THE 56TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2024, 2024, : 716 - 727
[4] Minors in Random and Expanding Hypergraphs
Wagner, Uli
COMPUTATIONAL GEOMETRY (SCG 11), 2011, : 351 - 360
[5] Explicit bounds for graph minors
Geelen, Jim
Huynh, Tony
Richter, R. Bruce
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2018, 132 : 80 - 106
[6] On matroid minors that guarantee their duals as minors
Taylor, Jesse
ADVANCES IN APPLIED MATHEMATICS, 2015, 71 : 14 - 33
[7] ALGORITHMS FOR RECOGNIZING BIPARTITE-HELLY AND BIPARTITE-CONFORMAL HYPERGRAPHS
Groshaus, Marina
Szwarcfiter, Jayme Luis
RAIRO-OPERATIONS RESEARCH, 2011, 45 (03) : 209 - 222
[8] CYCLABILITY IN BIPARTITE GRAPHS
Amar, Denise
Flandrin, Evelyne
Gancarzewicz, Grzegorz
OPUSCULA MATHEMATICA, 2009, 29 (04) : 345 - 364
[9] Cyclability and pancyclability in bipartite graphs
Abderrezzak, ME
Flandrin, E
Amar, D
DISCRETE MATHEMATICS, 2001, 236 (1-3) : 3 - 11
[10] On bipartite cages of excess 4
Filipovski, Slobodan
ELECTRONIC JOURNAL OF COMBINATORICS, 2017, 24 (01)

← 1 2 3 4 5 →