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 条

[21] Tabu search for the dynamic Bipartite Drawing Problem
Marti, Rafael
Martinez-Gavara, Anna
Sanchez-Oro, Jesus
Duarte, Abraham
COMPUTERS & OPERATIONS RESEARCH, 2018, 91 : 1 - 12
[22] BIPARTITE PERFECT MATCHING IS IN QUASI-NC
Fenner, Stephen
Gurjar, Rohit
Thierauf, Thomas
SIAM JOURNAL ON COMPUTING, 2021, 50 (03)
[23] The Connectivity of a Bipartite Graph and Its Bipartite Complementary Graph
Tian, Yingzhi
Ma, Huaping
Wu, Liyun
PARALLEL PROCESSING LETTERS, 2020, 30 (03)
[24] VERTEX-DISJOINT QUADRILATERALS IN BIPARTITE GRAPHS
YAN Jin LIU Guizhen (School of Mathematics & Systems Science
JournalofSystemsScienceandComplexity, 2004, (04) : 532 - 537
[25] Minors and internet gambling advertising: new formats, advertising content, and challenges in protecting minors
Martinez-Pastor, Esther
Vizcaino-Laorga, Ricardo
PROFESIONAL DE LA INFORMACION, 2021, 30 (04):
[26] Bipartite choices
LiCalzi, Marco
DECISIONS IN ECONOMICS AND FINANCE, 2022, 45 (02) : 551 - 568
[27] BIPARTITE RIGIDITY
Kalai, Gil
Nevo, Eran
Novik, Isabella
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2016, 368 (08) : 5515 - 5545
[28] Left loops, bipartite graphs with parallelism and bipartite involution sets
H. Karzel
S. Pianta
Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 2005, 75 : 203 - 214
[29] Left loops, bipartite graphs with parallelism and bipartite involution sets
Karzel, H
Pianta, S
ABHANDLUNGEN AUS DEM MATHEMATISCHEN SEMINAR DER UNIVERSITAT HAMBURG, 2005, 75 (1): : 203 - 214
[30] The Bipartite-Cylindrical Crossing Number of the Complete Bipartite Graph
Bernardo Ábrego
Silvia Fernández-Merchant
Athena Sparks
Graphs and Combinatorics, 2020, 36 : 205 - 220

← 1 2 3 4 5 →