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 条

[31] DOUBLE DOMINATING SEQUENCES IN BIPARTITE AND CO-BIPARTITE GRAPHS
Sharma, Gopika
Pandey, Arti
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2024, : 545 - 564
[32] MINORS AND VOLUNTEERING: PARTICIPATION AND SAFEGUARDS
Perez Monguio, Jose Maria
REVISTA GENERAL DE DERECHO ADMINISTRATIVO, 2023, (64):
[33] Human Dimensions of Chinese Minors
Zhang, Xin
Wang, Yanyu
Ran, Linghua
Feng, Ailan
He, Ketai
Liu, Taijie
Niu, Jianwei
DIGITAL HUMAN MODELING, 2011, 6777 : 37 - 45
[34] The extremal function for disconnected minors
Csoka, Endre
Lo, Irene
Norin, Sergey
Wu, Hehui
Yepremyan, Liana
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2017, 126 : 162 - 174
[35] Minors of a random binary matroid
Cooper, Colin
Frieze, Alan
Pegden, Wesley
RANDOM STRUCTURES & ALGORITHMS, 2019, 55 (04) : 865 - 880
[36] Transforms and Minors for Binary Functions
G. E. Farr
Annals of Combinatorics, 2013, 17 : 477 - 493
[37] On Minors of Maximal Determinant Matrices
Brent, Richard P.
Osborn, Judy-Anne H.
JOURNAL OF INTEGER SEQUENCES, 2013, 16 (04)
[38] Criminal mediation for minors in Israel
Kandel, Isack
Arie, Yael
Glasner, Sharon
THESCIENTIFICWORLDJOURNAL, 2007, 7 : 336 - 340
[39] A relationship between Minors and Linkages
Chen, Fuyuan
ARS COMBINATORIA, 2017, 133 : 317 - 327
[40] The Bipartite-Cylindrical Crossing Number of the Complete Bipartite Graph
Abrego, Bernardo
Fernandez-Merchant, Silvia
Sparks, Athena
GRAPHS AND COMBINATORICS, 2020, 36 (02) : 205 - 220

← 1 2 3 4 5 →