Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

On Stable Cutsets in Line Graphs

Van Bang LeContact Information and Bert RanderathContact Information

(5)  Fachbereich Informatik, Universität Rostock, D-18051 Rostock, Germany
(6)  Institut für Informatik, Universität zu Köln, D-50969 Köln, Germany
Abstract
We answer a question of Brandstädt et al. by showing that deciding whether a line graph with maximum degree 5 has a stable cutset is NP-complete. Conversely, the existence of a stable cutset in a line graph with maximum degree at most 4 can be decided efficiently. The proof of our NP-completeness result is based on a refinement on a result due to Chvátal that recognizing decomposable graphs with maximum degree 4 is an NP-complete problem. Here, a graph is decomposable if its vertices can be colored red and blue in such a way that each color appears on at least one vertex but each vertex v has at most one neighbor having a different color from v. We also discuss some open problems on stable cutsets.

Contact Information Van Bang Le
Email: le@informatik.uni-rostock.de

Contact Information Bert Randerath
Email: randerath@informatik.uni-koeln.de
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.107 • Server: mpweb21
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)