The complexity of the matchingcut problem for planar graphs and other graph classes
Bonsma, P.S. (2002) The complexity of the matchingcut problem for planar graphs and other graph classes. [Report]

PDF
234kB 
Abstract:  The MatchingCut problem is the problem to decide whether a graph has an edge cut that is also a matching. Chvtal studied this problem under the name of the Decomposable Graph Recognition problem, and proved the problem to be complete for graphs with maximum degree 4, and gave a polynomial algorithm for graphs with maximum degree 3. Recently, unaware of Chvtal's result, Patrignani and Pizzonia also proved the completeness of the problem using a different reduction. They also posed the question whether the MatchingCut problem is complete for planar graphs. In this paper an affirmative answer is given. Moreover, it is shown that the problem remains complete when restricted to planar bipartite graphs, planar graphs with girth 5 and planar graphs with maximum degree 4, making this the strongest result to date. The reduction is from Planar Graph 3Colorability and differs from the reductions used to prove the earlier results.

Item Type:  Report 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/65841 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page