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, ori interval graphs and bipartite permutation graphs, and also NP-haxd cases, for example, on grid graphs and chordal graphs.
展开▼
