## RenĂ© van Bevern, Robert Bredereck, Laurent Bulteau, Jiehua Chen, Vincent
Froese, Rolf Niedermeier, and Gerhard J. Woeginger.
Partitioning perfect graphs into stars.
*Journal of Graph Theory*, 85(2):297–335, 2017.

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 of the same size, 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 cases, for example, on
interval graphs and bipartite permutation graphs,
and also NP-complete cases, for example, on grid
graphs and chordal graphs.

[ bib |
DOI |
http ]
Back

*This file was generated by
bibtex2html 1.98.*