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 language | English |
|---|
| Publisher | s.n. |
|---|
| Number of pages | 37 |
|---|
| Publication status | Published - 2014 |
|---|
| Name | arXiv |
|---|
| Volume | 1402.2589 [cs.DM] |
|---|