Bipartizing with a Matching

We study the problem of determining whether a given graph \(G=(V,E)\) admits a matching M whose removal destroys all odd cycles of G (or equivalently whether \(G-M\) is bipartite). This problem is equivalent to determine whether G admits a (2, 1)-coloring, which is a 2-coloring of V(G) in which each color class induces a graph of maximum degree at most 1. We determine a dichotomy related to the NP-completeness of such a decision problem, where it is NP-complete even for 3-colorable planar graphs of maximum degree 4, while it is linear-time solvable for graphs of maximum degree at most 3. In addition, we present polynomial-time algorithms for many graph classes including those in which every odd-cycle subgraph is a triangle, graphs having bounded dominating sets, and \(P_5\)-free graphs. Additionally, we show that this problem is fixed-parameter tractable when parameterized by the clique-width, which implies that it is polynomial-time solvable for many interesting graph classes, such as distance-hereditary, outerplanar, and chordal graphs.