Advertisement
Published in:
2005 | OriginalPaper | Chapter
On Stable Cutsets in Claw-Free Graphs and Planar Graphs
Authors : Van Bang Le, Raffaele Mosca, Haiko Müller
Published in: Graph-Theoretic Concepts in Computer Science
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
To decide whether a line graph (hence a claw-free graph) of maximum degree five admits a stable cutset has been proven to be an
NP
-complete problem. The same result has been known for
K
4
-free graphs. Here we show how to decide this problem in polynomial time for (claw,
K
4
)-free graphs and for a claw-free graph of maximum degree at most four. As a by-product we prove that the stable cutset problem is polynomially solvable for claw-free planar graphs, and for planar line graphs. Now, the computational complexity of the stable cutset problem restricted to claw-free graphs and claw-free planar graphs is known for all bounds on the maximum degree.
Moreover, we prove that the stable cutset problem remains
NP
-complete for
K
4
-free planar graphs of maximum degree five.