### Abstract

Original language | English |
---|---|

Pages (from-to) | 567-575 |

Number of pages | 9 |

Journal | European journal of combinatorics |

Volume | 34 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2013 |

### Fingerprint

### Keywords

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

### Cite this

*European journal of combinatorics*,

*34*(3), 567-575. https://doi.org/10.1016/j.ejc.2011.09.044

}

*European journal of combinatorics*, vol. 34, no. 3, pp. 567-575. https://doi.org/10.1016/j.ejc.2011.09.044

**Fully decomposable split graphs.** / Broersma, Haitze J.; Kratsch, Dieter; Woeginger, Gerhard.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - Fully decomposable split graphs

AU - Broersma, Haitze J.

AU - Kratsch, Dieter

AU - Woeginger, Gerhard

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - EWI-22740

KW - MSC-05C

KW - Fully decomposable

KW - Arbitrarily vertex decomposable

KW - Partitioning

KW - METIS-296435

KW - IR-83468

KW - Split graph

U2 - 10.1016/j.ejc.2011.09.044

DO - 10.1016/j.ejc.2011.09.044

M3 - Article

VL - 34

SP - 567

EP - 575

JO - European journal of combinatorics

JF - European journal of combinatorics

SN - 0195-6698

IS - 3

ER -