On the computational complexity of the bipartizing matching problem
2021
Given a graph $$G=(V,E)$$
, an edge bipartization set of G is a subset $$E'\subseteq E(G)$$
such that
$$G'=(V,E{\setminus } E')$$
is bipartite. An edge bipartization set that is also a matching of G is called a bipartizing matching of G. Let
$${\mathscr {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}$$
) 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$$
, the k-coloring is non-proper, also known as defective. A graph belongs to
$$\mathscr {BM}$$
if and only if it admits a (2, 1)-coloring. Lovasz (1966) proved that for any integer
$$k>0$$
, any graph of maximum degree
$$\varDelta $$
admits a
$$\left( k,\lfloor \varDelta /k \rfloor \right) $$
-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}$$
, 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 Lovasz (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}}$$
.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
48
References
0
Citations
NaN
KQI