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

84 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]

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

  • Cite this

    Bevern, van, R., Bredereck, R., Bulteau, L., Chen, J., Froese, V., Niedermeier, R., & Woeginger, G. J. (2014). Star partitions of perfect graphs. (arXiv; Vol. 1402.2589 [cs.DM]). s.n.