Abstract
The Matching-Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Previously this problem was studied under the name of the Decomposable Graph Recognition problem, and proved to be -complete when restricted to graphs with maximum degree four. In this paper it is shown that the problem remains -complete for planar graphs with maximum degree four, answering a question by Patrignani and Pizzonia. It is also shown that the problem is -complete for planar graphs with girth five. The reduction is from planar graph 3-colorability and differs from earlier reductions. In addition, for certain graph classes polynomial time algorithms to find matching-cuts are described. These classes include claw-free graphs, co-graphs, and graphs with fixed bounded tree-width or clique-width.
Original language | Undefined |
---|---|
Pages (from-to) | 109-126 |
Journal | Journal of graph theory |
Volume | 62 |
Issue number | 2 |
DOIs | |
Publication status | Published - 2009 |
Keywords
- IR-72723
- Planar graph
- Matching-cut
- Computational Complexity
- decomposable graph