Bipartite minors

DOI10.1016/J.JCTB.2015.08.001zbMATH Open1327.05315DBLPjournals/jct/ChudnovskyKNNS16arXiv1312.0210OpenAlexW2913147187WikidataQ56235103 ScholiaQ56235103MaRDI QIDQ896000FDOQ896000

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)

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.

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

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

zbMATH Keywords

planar graphsbipartite graphsouterplanar graphsminorsKuratowski's theoremLaman graphsbipartite minorsperipheral cycles

Mathematics Subject Classification ID

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

Cites Work

• On graphs and rigidity of plane skeletal structures
• Über eine Eigenschaft der ebenen Komplexe
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bipartite rigidity

Cited In (10)

• Bipartite rigidity
• Minors for alternating dimaps
• Interval minors of complete bipartite graphs
• A note on immersion minors and planarity
• Title not available (Why is that?)
• Excluded checkerboard colourable ribbon graph minors
• Bipartite rigidity
• Bipartite and Eulerian minors
• Extremal embedded 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)