Note
Matching cutsets in graphs of diameter 2

https://doi.org/10.1016/j.tcs.2008.07.002Get rights and content
Under an Elsevier user license
open archive

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.

Keywords

Matching cutset
Stable cutset
Graph algorithms

Cited by (0)