Affiliation: | aInstitut für Informatik, Universität Rostock, 18051 Rostock, Germany bDipartimento di Scienze, Universitá degli Studi “G.D'Annunzio”, Viale Pindaro 42, Pescara 65127, Italy cSchool of Computing, University of Leeds, Leeds, LS2 9JT, UK |
Abstract: | A stable cutset in a connected graph is a stable set whose deletion disconnects the graph. Let and (claw) denote the complete (bipartite) graph on 4 and vertices. It is NP-complete to decide whether a line graph (hence a claw-free graph) with maximum degree five or a -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, )-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 -free planar graphs with maximum degree five. |