Complexity of cubic graph decomposition
It turns out that the problem is eqivalent to the 1-perfect code problem in cubic graphs. Therefore, Deciding the existence of decomposition of a cubic graph into vertex disjoint claws is NP-complete.