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.