| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 438100 | Theoretical Computer Science | 2008 | 9 Pages |
Abstract
We say that a graph has a matching cutset if its vertices can be coloured in red and blue in such a way that there exists at least one vertex coloured in red and at least one vertex coloured in blue, and every vertex has at most one neighbour coloured in the opposite colour. In this paper we study the algorithmic complexity of a problem of recognizing graphs which possess a matching cutset. In particular we present a polynomial-time algorithm which solves this problem for graphs of diameter two.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
