On stable cutsets in claw-free graphs and planar graphs

A stable cutset in a connected graph is a stable set whose deletion disconnects the graph. Let K-4 and K-1,K-3 (claw) denote the complete (bipartite) graph on 4 and 1 + 3 vertices. It is NP-complete to decide whether a line graph (hence a claw-free graph) with maximum degree five or a K-4-free graph admits a stable cutset. Here we describe algorithms deciding in polynomial time whether a claw-free graph with maximum degree at most four or whether a (claw, K-4)-free graph admits a stable cutset. As a by-product we obtain that the stable cutset problem is polynomially solvable for claw-free planar graphs, and also for planar line graphs. Thus, the computational complexity of the stable cutset problem is completely determined for claw-free graphs with respect to degree constraint, and for claw-free planar graphs. Moreover, we prove that the stable cutset problem remains NP-complete for K-4-free planar graphs with maximum degree five. (C) 2008 Elsevier B.V. All rights reserved.