Fully decomposable split graphs

Broersma, H.J.; Kratsch, D.; Woeginger, G.J.

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, i.e., whether it can be partitioned into connected parts of order α₁,α₂,...,αk for every α₁,α₂,...,α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 order α₁,α₂,...,αk for a given partition α₁,α₂,...,αk of the order of the graph, is NP-hard.

Citation

Broersma, H., Kratsch, D., & Woeginger, G. (2023, June). Fully decomposable split graphs. Presented at 20th International Workshop on Combinatorial Algorithms (IWOCA 2009), Hradec nad Moravicí, Czech Republic

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 20th International Workshop on Combinatorial Algorithms (IWOCA 2009)
• Start Date: Jun 28, 2023
• End Date: Jul 2, 2009
• Publication Date: Nov 1, 2009
• Deposit Date: Mar 1, 2010
• Print ISSN: 0302-9743
• Pages: 105-112
• Series Title: Lecture notes in computer science
• Series Number: 5874
• Series ISSN: 0302-9743
• Book Title: Combinatorial algorithms : 20th International Workshop, IWOCA 2009, 28 June - 2 July 2009, Hradec nad Moravicí, Czech Republic ; revised selected papers.
• DOI: https://doi.org/10.1007/978-3-642-10217-2_13
• Keywords: Graph decomposition, Integer partition, Computational complexity.
• Public URL: https://durham-repository.worktribe.com/output/1697657