On the computational complexity of the bipartizing matching problem

Given a graph $$G=(V,E)$$ G = ( V , E ) , an edge bipartization set of G is a subset $$E'\subseteq E(G)$$ E ′ ⊆ E ( G ) such that $$G'=(V,E{\setminus } E')$$ G ′ = ( V , E \ E ′ ) is bipartite. An edge bipartization set that is also a matching of G is called a bipartizing matching of G. Let $${\mathscr {BM}}$$ BM be the family of all graphs admitting a bipartizing matching. Although every graph has an edge bipartization set, the problem of recognizing graphs G having bipartizing matchings ( $$G\in \mathscr {BM}$$ G ∈ BM ) is challenging. A (k, d)-coloring of a graph G is a k-coloring of V(G) such that each vertex of G has at most d neighbors with the same color as itself. Clearly a (k, 0)-coloring is a proper vertex k-coloring of G and, for any $$d>0$$ d > 0 , the k-coloring is non-proper, also known as defective. A graph belongs to $$\mathscr {BM}$$ BM if and only if it admits a (2, 1)-coloring. Lovász (1966) proved that for any integer $$k>0$$ k > 0 , any graph of maximum degree $$\varDelta $$ Δ admits a $$\left( k,\lfloor \varDelta /k \rfloor \right) $$ k , ⌊ Δ / k ⌋ -coloring. In this paper, we show that it is NP-complete to determine whether a 3-colorable planar graph of maximum degree 4 belongs to $$\mathscr {BM}$$ BM , i.e., (2, 1)-colorable. Besides, we show that it is NP-complete to determine whether planar graphs of maximum degree 6 or 8 admit a (2, 2) or (2, 3)-coloring, respectively. Due to Lovász (1966), our results are tight in the sense that on graphs with maximum degree three, five, and seven, there always exists a (2, 1), (2, 2), and (2, 3)-coloring, respectively. Finally, we present polynomial-time algorithms for particular graph classes, besides some remarks on the parameterized complexity of the problem of recognizing graphs in $${\mathscr {BM}}$$ BM .