Bipartite minors

DOI10.1016/J.JCTB.2015.08.001MaRDI QIDQ896000zbMATH OpenOpenAlexDBLPWikidataFDO

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

Publication date 11 December 2015

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.0210

zbMATH Keywords

bipartite graphsbipartite minorsKuratowski's theoremLaman graphsminorsouterplanar graphsperipheral cyclesplanar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83)

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.

Recommendations

• Bipartite and Eulerian minors
• Interval minors of complete bipartite graphs
• scientific article; zbMATH DE number 4095479
• Graph minors. V. Excluding a planar graph
• Topological minors in bipartite graphs

Cites work

• Bipartite rigidity
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 3259770 (Why is no real title available?)
• On graphs and rigidity of plane skeletal structures
• Über eine Eigenschaft der ebenen Komplexe

Cited in

(11)

• Bipartite and Eulerian minors
• A note on immersion minors and planarity
• Excluded checkerboard colourable ribbon graph minors
• Bipartite rigidity
• Interval minors of complete bipartite graphs
• Bipartite rigidity
• scientific article; zbMATH DE number 4095479 (Why is no real title available?)
• Minors for alternating dimaps
• Extremal embedded graphs
• Recursive characterization of maximal bipartite planar graphs
• Eulerian and even-face ribbon graph minors

This page was built for publication: Bipartite minors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896000)