[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

On Stable Cutsets in Claw-Free Graphs and Planar Graphs

  • Conference paper
Graph-Theoretic Concepts in Computer Science (WG 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3787))

Included in the following conference series:

  • 1123 Accesses

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bonsma, P.: The complexity of the matching-cut problem for planar graphs and other graph classes. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 93–105. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  2. Brandstädt, A., Dragan, F., Le, V.B., Szymczak, T.: On stable cutsets in graphs. Discr. Appl. Math. 105, 39–50 (2000)

    Article  MATH  Google Scholar 

  3. Chen, G., Faudree, R.J., Jacobson, M.S.: Fragile graphs with small independent cuts. J. Graph Theory 41, 327–341 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  4. Chen, G., Yu, X.: A note on fragile graphs. Discrete Math. 249, 41–43 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  5. Chvátal, V.: Recognizing decomposable Graphs. J. Graph Theory 8, 51–53 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  6. Corneil, D.G., Fonlupt, J.: Stable set bonding in perfect graphs and parity graphs. J. Combin. Theory (B) 59, 1–14 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  7. di Battista, G., Patrignani, M., Vargiu, F.: A Split&Push approach to 3D orthogonal drawing. J. Graph Algorithms Appl. 1, 105–133 (2000)

    Google Scholar 

  8. Farley, A.M., Proskurowski, A.: Networks immune to isolated line failures. Networks 12, 393–403 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  9. Farley, A.M., Proskurowski, A.: Extremal graphs with no disconnecting matching. Congressus Nummerantium 41, 153–165 (1984)

    MathSciNet  Google Scholar 

  10. Feder, T., Hell, P., Klein, S., Motwani, R.: List partitions. SIAM J. Discrete Math. 16, 449–478 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  11. Graham, R.L.: On primitive graphs and optimal vertex assigments. Ann. N.Y. Acad. Sci. 175, 170–186 (1970)

    MATH  Google Scholar 

  12. Hemminger, R.L., Beineke, L.W.: Line graphs and line digraphs. In: Beineke, L.W., Wilson, R.T. (eds.) Selected Topics in Graph Theory I, pp. 271–305. Academic Press, London (1978)

    Google Scholar 

  13. Klein, S., de Figueiredo, C.M.H.: The NP-completeness of multi-partite cutset testing. Congressus Numerantium 119, 217–222 (1996)

    MATH  MathSciNet  Google Scholar 

  14. Lichtenstein, D.: Planar formulae and their uses. SIAM Journal on Computing 11, 320–343 (1982)

    Article  MathSciNet  Google Scholar 

  15. Le, V.B., Randerath, B.: On stable cutsets in line graphs. Theor. Comput. Sci. 301, 463–475 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  16. Moshi, A.M.: Matching cutsets in graphs. J. Graph Theory 13, 527–536 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  17. Patrignani, M., Pizzonia, M.: The complexity of the matching-cut problem. In: Brandstädt, A., Le, V.B. (eds.) WG 2001. LNCS, vol. 2204, pp. 284–295. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  18. Tarjan, R.E.: Decomposition by clique separators. Discr. Math. 55, 221–232 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  19. Tollis, I., di Battista, G., Eades, P., Tamassia, R.: Graph drawing. Algorithms for the visualization of graphs. Prentice Hall, Upper Saddle River (1999)

    MATH  Google Scholar 

  20. Tucker, A.: Coloring graphs with stable cutsets. J. Combin. Theory (B) 34, 258–267 (1983)

    Article  MATH  Google Scholar 

  21. Whitesides, S.H.: An algorithm for finding clique cut-sets. Inf. Process. Lett. 12, 31–32 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  22. Whitesides, S.H.: An method for solving certain graph recognition and optimization problems, with applications to perfect graphs. Ann. Discr. Math. 21, 281–297 (1984)

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Informatik, Universität Rostock, 18051, Rostock, Germany

    Van Bang Le

  2. Dipartimento di Scienze, Universitá degli Studi “G.D’Annunzio”, Viale Pindaro 42, Pescara, 65127, Italy

    Raffaele Mosca

  3. School of Computing, University of Leeds, Leeds, LS2 9JT, UK

    Haiko Müller

Authors
  1. Van Bang Le
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Raffaele Mosca
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Haiko Müller
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. LITA, Université Paul Verlaine-Metz, 57045, Metz Cedex 01, France

    Dieter Kratsch

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Le, V.B., Mosca, R., Müller, H. (2005). On Stable Cutsets in Claw-Free Graphs and Planar Graphs. In: Kratsch, D. (eds) Graph-Theoretic Concepts in Computer Science. WG 2005. Lecture Notes in Computer Science, vol 3787. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11604686_15

Download citation

  • DOI: https://doi.org/10.1007/11604686_15

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-31000-6

  • Online ISBN: 978-3-540-31468-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation