Bipartite minors

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

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

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

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

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

Cited In (8)

• Bipartite rigidity
• Minors for alternating dimaps
• A note on immersion minors and planarity
• Excluded checkerboard colourable ribbon graph minors
• Bipartite and Eulerian minors
• Extremal embedded graphs
• Eulerian and even-face ribbon graph minors
• Bipartite Rigidity

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)