Complexity of cubic graph decomposition

I am aware that deciding the existence of decomposition of a cubic graph into edge-disjoint claws is polynomial time solvable. Since a cubic graph has a decomposition into edge-disjoint claws if and only if it is bipartite.


What is the complexity of deciding the existence of decomposition of a cubic graph into vertex disjoint claws? Is it NP-complete?

In the former problem, we partition the edge set into edge-disjoint claws while in the later one we partition the vertex set into vertex-disjoint claws.

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.

StackExchange Computer Science Q#44770, answer score: 2