distance to bipartite

equivalent to: odd cycle transversal, distance to bipartite

Relations

Results

• 2022 Expanding the Graph Parameter Hierarchy by Tran
  • 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 Chordal Bipartite Graphs with High Boxicity by Chandran, Francis, Mathew
  • 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$.
• unknown source
  • odd cycle transversal is equivalent to distance to bipartite – Bipartite graphs is the graph class without any odd cycles.
  • distance to bipartite is equivalent to odd cycle transversal – Bipartite graphs is the graph class without any odd cycles.
  • distance to bipartite upper bounds chromatic number by a linear function – Removed vertices get one color each and we need only $2$ colors for the rest.
• Comparing Graph Parameters by Schröder
  • 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
• assumed
  • graph class bipartite has constant distance to bipartite – by definition