Bipartite Minors

2013/12/01 by Maria Chudnovsky, Gil Kalai, Chudnovsky, Maria +7
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1312.0210

openalex publication_date 2013/12/01 · openalex created_date 2022/09/02 · openalex updated_date 2026/07/28

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.

Related

• Forbidden minors: Finding the finite few
• Graphs without large K_2,n-minors
• Excluding a Planar Matching Minor in Bipartite Graphs
• Universal planar graphs for the topological minor relation
• A characterization of K_2,4-minor-free graphs