4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.