## RenĂ© van Bevern, Robert Bredereck, Laurent Bulteau, Jiehua Chen, Vincent
Froese, Rolf Niedermeier, and Gerhard J. Woeginger.
Star partitions of perfect graphs.
In *Proceedings of the 41st International Colloquium on Automata,
Languages, and Programming (ICALP'14), Copenhagen, Denmark*, volume 8572 of
*Lecture Notes in Computer Science*, pages 174–185. Springer, 2014.
The final version of this article appeared in Journal of Graph
Theory.

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 cases, for example, on interval graphs and
bipartite permutation graphs, and also NP-hard cases,
for example, on grid graphs and chordal graphs.

[ bib |
DOI |
journal version ]
Back

*This file was generated by
bibtex2html 1.98.*