Star partitions of perfect graphs

R. Bevern, van, R. Bredereck, L. Bulteau, J. Chen, V. Froese, R. Niedermeier, G.J. Woeginger

Research output: Book/ReportReportAcademic

103 Downloads (Pure)


The partition of graphs into nice subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into stars, a problem known to be NP-complete even for the case of stars on three vertices. We perform a thorough computational complexity study of the problem on subclasses of perfect graphs and identify several polynomial-time solvable and NP-hard cases, for example, on interval graphs, grid graphs, and bipartite permutation graphs.
Original languageEnglish
Number of pages37
Publication statusPublished - 2014

Publication series

Volume1402.2589 [cs.DM]


Dive into the research topics of 'Star partitions of perfect graphs'. Together they form a unique fingerprint.

Cite this