distance to bipartite

• 2022/09 Tran2022
  • page 38 : bounded twin-width does not imply bounded distance to bipartite – Proposition 6.6. Twin-width is incomparable to Distance to Bipartite.
  • page 38 : bounded distance to bipartite does not imply bounded twin-width – Proposition 6.6. Twin-width is incomparable to Distance to Bipartite.
• 2011 bipboxicity2011
  • page 9 : bounded distance to bipartite does not imply bounded boxicity – Theorem 2 For any $b \in \mathbb N^+$, there exists a chordal bipartite graph $G$ (ed: i.e. bipartite graph with no induced cycle on more than 4 vertices) with $\mathrm{box}(G) > b$.
• SchroderThesis
  • page 20 : bounded distance to bipartite does not imply bounded distance to chordal – Proposition 3.12
  • page 20 : bounded distance to bipartite does not imply bounded vertex connectivity – Proposition 3.12
  • page 20 : bounded distance to bipartite does not imply bounded domatic number – Proposition 3.12
  • page 28 : bounded distance to bipartite does not imply bounded clique-width – Proposition 3.26
  • page 28 : bounded distance to bipartite does not imply bounded bisection bandwidth – Proposition 3.26
• unknown
  • bipartite upper bounds distance to bipartite by a constant – by definition
  • odd cycle transversal is equal to distance to bipartite – Bipartite graphs is the graph class without any odd cycles.
  • distance to bipartite $k$ upper bounds chromatic number by $\mathcal O(k)$ – Removed vertices get one color each and we need only $2$ colors for the rest.