Bipartite minors

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

Research output: Contribution to journalArticle

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

Original languageEnglish (US)
Pages (from-to)219-228
Number of pages10
JournalJournal of Combinatorial Theory. Series B
Volume116
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'Bipartite minors'. Together they form a unique fingerprint.

  • Cite this