Abstract
The Matching-Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Chvátal 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. In this paper it is shown that the problem is -complete when restricted to planar graphs with girth 5 and planar graphs with maximum degree 4. In addition, for claw-free graphs and planar graphs with girth at least 7 polynomial algorithms to find matching-cuts are described.
| Original language | English |
|---|---|
| Title of host publication | Graph-Theoretic Concepts in Computer Science |
| Subtitle of host publication | 29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers |
| Editors | Hans L. Bodlaender |
| Publisher | Springer |
| Pages | 93-105 |
| ISBN (Electronic) | 978-3-540-39890-5 |
| ISBN (Print) | 978-3-540-20452-7 |
| DOIs | |
| Publication status | Published - 2003 |
| Event | 29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2003 - Elspeet, Netherlands Duration: 19 Jun 2003 → 21 Jun 2003 Conference number: 29 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer-Verlag |
| Volume | 2880 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Workshop
| Workshop | 29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2003 |
|---|---|
| Abbreviated title | WG |
| Country/Territory | Netherlands |
| City | Elspeet |
| Period | 19/06/03 → 21/06/03 |
Keywords
- IR-72724
- METIS-214384