𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The complexity of the matching-cut problem for planar graphs and other graph classes

✍ Scribed by Paul Bonsma

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
247 KB
Volume
62
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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
${\cal{NP}}$‐complete when restricted to graphs with maximum degree four. In this paper it is shown that the problem remains
${\cal{NP}}$‐complete for planar graphs with maximum degree four, answering a question by Patrignani and Pizzonia. It is also shown that the problem is
${\cal{NP}}$‐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. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 109–126, 2009

📜 SIMILAR VOLUMES

On the max-cut problem for a planar, cub
On the max-cut problem for a planar, cubic, triangle-free graph, and the Chinese postman problem for a planar triangulation
✍ Carsten Thomassen 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 2 views

## Abstract Every 3‐connected planar, cubic, triangle‐free graph with __n__ vertices has a bipartite subgraph with at least 29__n__/24 − 7/6 edges. The constant 29/24 improves the previously best known constant 6/5 which was considered best possible because of the graph of the dodecahedron. Example

A branch and cut algorithm for the Stein
A branch and cut algorithm for the Steiner problem in graphs
✍ Lucena, A.; Beasley, J. E. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 165 KB 👁 2 views

In this paper, we consider the Steiner problem in graphs, which is the problem of connecting together, at minimum cost, a number of vertices in an undirected graph with nonnegative edge costs. We use the formulation of this problem as a shortest spanning tree (SST) problem with additional constraint

Optimal Ear Decompositions of Matching C
Optimal Ear Decompositions of Matching Covered Graphs and Bases for the Matching Lattice
✍ Marcelo H. de Carvalho; Cláudio L. Lucchesi; U.S.R. Murty 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 225 KB

A Petersen brick is a graph whose underlying simple graph is isomorphic to the Petersen graph. For a matching covered graph G, b(G) denotes the number of bricks of G, and p(G) denotes the number of Petersen bricks of G. An ear decomposition of G is optimal if, among all ear decompositions of G, it u

The Structure of Well-Covered Graphs and
The Structure of Well-Covered Graphs and the Complexity of Their Recognition Problems
✍ David Tankus; Michael Tarsi 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 449 KB

A graph is well-covered if all its maximal independent sets are of the same cardinality. Deciding whether a given graph is well-covered is known to be NP-hard in general, and solvable in polynomial time, if the input is restricted to certain families of graphs. We present here a simple structural ch

On quadrilaterals in layers of the cube
On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs
✍ Schelp, Richard H.; Thomason, Andrew 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 286 KB 👁 2 views

Erdős has conjectured that every subgraph of the n-cube Q n having more than (1/2+o(1))e(Q n ) edges will contain a 4-cycle. In this note we consider 'layer' graphs, namely, subgraphs of the cube spanned by the subsets of sizes k -1, k and k + 1, where we are thinking of the vertices of Q n as being