bipartite

• 2017 Diestel2017
  • page 17 : bipartite – Instead of `2-partite’ one usually says bipartite.
• 1993 BodlaenderMohring1993
  • page 4 : graph class bipartite has unbounded treewidth – Lemma 3.2 (“complete bipartite subgraph containment lemma”).
• assumed
  • bipartite upper bounds perfect by a constant
  • graph class perfect is not included in graph class bipartite
  • forest upper bounds bipartite by a constant
  • graph class bipartite is not included in graph class forest
  • grid upper bounds bipartite by a constant
  • graph class bipartite is not included in graph class grid
• unknown
  • bipartite upper bounds distance to bipartite by a constant – by definition
  • maximum matching on bipartite graphs $k$ upper bounds bipartite by $\mathcal O(k)$ – by definition
  • graph class bipartite has unbounded girth
  • graph class bipartite has unbounded edge connectivity