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 条

[41] Forcibly bipartite and acyclic (uni-)graphic sequences
Bar-Noy, Amotz
Bohnlein, Toni
Peleg, David
Rawitz, Dror
DISCRETE MATHEMATICS, 2023, 346 (07)
[42] CONTENT OF CORRECTIONAL WORKS FOR MINORS
Rogova, Ye, V
RUSSIAN JOURNAL OF CRIMINOLOGY, 2011, (03): : 20 - 27
[43] BOUNDS ON MINORS OF BINARY MATRICES
Brent, Richard P.
Osborn, Judy-Anne H.
BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY, 2013, 88 (02) : 280 - 285
[44] Defective Coloring is Perfect for Minors
Liu, Chun-Hung
COMBINATORICA, 2024, 44 (03) : 467 - 507
[45] ASSESSING MENTAL DISABILITY IN MINORS
Mozes, T.
Tyano, S.
MEDICINE AND LAW, 2006, 25 (02): : 297 - 317
[46] Infinite Gammoids: Minors and Duality
Borujeni, Seyed Hadi Afzali
Law, Hiu-Fai
Mueller, Malte
ELECTRONIC JOURNAL OF COMBINATORICS, 2015, 22 (04)
[47] Civil responsibility in the field of minors
Ramon Fernandez, Francisca
REVISTA SOBRE LA INFANCIA Y LA ADOLESCENCIA, 2012, (03) : 1 - 23
[48] PROCEDURAL IMPRESSIONS ABOUT MINORS
Bueno Ochoa, Luis
CUADERNOS ELECTRONICOS DE FILOSOFIA DEL DERECHO, 2013, (28): : 58 - 78
[49] COMPLETE MINORS AND INDEPENDENCE NUMBER
Fox, Jacob
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (04) : 1313 - 1321
[50] A note on immersion minors and planarity
Wagner, Donald K.
DISCRETE MATHEMATICS, 2018, 341 (06) : 1605 - 1612

← 1 2 3 4 5 →