Is it NP-hard to partition the vertex set of graph G into k subsets so that they induce k claw-free subgraphs of G?


It is NP-hard, even for $k=2$.

This is a special case of a theorem by Farrugia (Alastair Farrugia, Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard, The electronic journal of combinatorics 11 (2004), #R46), stating that it is NP-complete to test if the vertex set a graph can be partitioned into two subsets A and B such that G(A) belongs to the graph class P and G(B) belongs to the graph class Q, provided P and Q are closed under taking vertex-disjoint unions and talking induced subgraphs, and at least one of P and Q is non-trivial (meaning not all graphs in the class are edgeless).


It's NP-complete for any number three or more of subgraphs.

Suppose you have a graph $G$ for which 3-coloring is hard. Then partitioning $G\times K_7$ into three claw-free induced subgraphs is also hard.

Here, $\times$ is the tensor product of graphs. Each vertex of $G$ is blown up into an independent set of size $7$, and each edge of $G$ is blown up into a subgraph $K_{7,7}$.

Given a coloring of $G$, you can partition it into claw-free induced subgraphs (actually, independent sets, but independent sets are claw-free) by applying the same coloring to $G\times K_7$. On the other hand, suppose you have a claw-free partition of $G\times K_7$; then for each vertex $v$ of $G$ choose a subgraph of the partition that has at least three vertices of $v\times K_7$ and use that choice to color $v$. The result should be a proper coloring, because if not it contains a claw (actually, a $K_{3,3}$, but $K_{3,3}$ contains a claw).

The same reduction (using a tensor product with a larger complete graph) works for partitioning into any larger number of claw-free induced subgraphs. I suspect that even partitioning into two claw-free induced subgraphs is hard, but that would take a different proof.

  • $\begingroup$ Nice proof. The case for two would follow from 3 being hard. If we could solve it for two, we could solve it for three. On the other hand: S. Burr, P. Erdos and L. Lovisz, On graphs of Ramsey type, Ars Combin. 1 (1976) 167-190 Theorem 9 gives a necessary and sufficient condition for edge 2-coloring stars. If max_deg(G) >= 2n-1 then any coloring would result in monochromatic n-star. So for any max_deg(G) < 5 we could easily break G into 2 claw-free subgraphs. $\endgroup$ – Jaanus Käärmann Dec 11 '15 at 19:38

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.