# Partition graph into 2 or more claw-free subgraphs

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.

• 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. – Jaanus Käärmann Dec 11 '15 at 19:38