Eliminating Odd Cycles by Removing a Matching
share
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 also equivalent to determine whether G admits a (1,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 show that such a decision problem is NP-complete even for planar graphs of maximum degree 4, but can be solved in linear-time in graphs of maximum degree 3. We also present polynomial time algorithms for (claw, paw)-free graphs, graphs containing only triangles as odd cycles, graphs with bounded dominating sets, P_5-free graphs, and chordal graphs. In addition, we show that the problem is fixed-parameter tractable when parameterized by clique-width, which implies polynomial time solvability for many interesting graph classes of such as distance-hereditary graphs and outerplanar graphs. Finally, a 2^vc(G)· n algorithm, and a kernel having at most 2· nd(G) vertices are presented, where vc(G) and nd(G) are the vertex cover number and the neighborhood diversity of the input graph, respectively.
READ FULL TEXT