Bipartite minors

Maria Chudnovsky; Gil Kalai; Eran Nevo; Isabella Novik; Paul Seymour

doi:10.1016/j.jctb.2015.08.001

Bipartite minors

Maria Chudnovsky, Gil Kalai, Eran Nevo, Isabella Novik, Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

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 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.

Original language	English (US)
Pages (from-to)	219-228
Number of pages	10
Journal	Journal of Combinatorial Theory. Series B
Volume	116
DOIs	https://doi.org/10.1016/j.jctb.2015.08.001
State	Published - Jan 2016

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

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

Access to Document

10.1016/j.jctb.2015.08.001

Cite this

@article{766bd90dd29d4683bbfce130d6b4ca85,

title = "Bipartite minors",

abstract = "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 K3,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.",

keywords = "Bipartite graphs, Bipartite minors, Kuratowski's theorem, Laman graphs, Minors, Peripheral cycles, Planar and outerplanar graphs",

author = "Maria Chudnovsky and Gil Kalai and Eran Nevo and Isabella Novik and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier Inc.",

year = "2016",

month = jan,

doi = "10.1016/j.jctb.2015.08.001",

language = "English (US)",

volume = "116",

pages = "219--228",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Bipartite minors

AU - Chudnovsky, Maria

AU - Kalai, Gil

AU - Nevo, Eran

AU - Novik, Isabella

AU - Seymour, Paul

PY - 2016/1

Y1 - 2016/1

N2 - 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 K3,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.

AB - 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 K3,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.

KW - Bipartite graphs

KW - Bipartite minors

KW - Kuratowski's theorem

KW - Laman graphs

KW - Minors

KW - Peripheral cycles

KW - Planar and outerplanar graphs

UR - https://www.scopus.com/pages/publications/84947568933

UR - https://www.scopus.com/inward/citedby.url?scp=84947568933&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2015.08.001

DO - 10.1016/j.jctb.2015.08.001

M3 - Article

AN - SCOPUS:84947568933

SN - 0095-8956

VL - 116

SP - 219

EP - 228

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Bipartite minors

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this