Fully decomposable split graphs

Haitze J. Broersma, Dieter Kratsch, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
39 Downloads (Pure)

Abstract

We discuss various questions around partitioning a split graph into connected parts. Our main result is a polynomial time algorithm that decides whether a given split graph is fully decomposable, that is, whether it can be partitioned into connected parts of orders α1,α2,...,αk for every α1,α2,...,αk summing up to the order of the graph. In contrast, we show that the decision problem whether a given split graph can be partitioned into connected parts of orders α1,α2,...,αk for a given partition α1,α2,...,αk of the order of the graph, is NP-hard.
Original languageEnglish
Pages (from-to)567-575
Number of pages9
JournalEuropean journal of combinatorics
Volume34
Issue number3
DOIs
Publication statusPublished - 2013

Keywords

  • EWI-22740
  • MSC-05C
  • Fully decomposable
  • Arbitrarily vertex decomposable
  • Partitioning
  • METIS-296435
  • IR-83468
  • Split graph

Fingerprint Dive into the research topics of 'Fully decomposable split graphs'. Together they form a unique fingerprint.

Cite this