<p>It is NP-hard, even for $k=2$.</p>

<p>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), <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r46">#R46</a>), 
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). </p>

CC BY-SA 3.0
2015-12-11T19:53:50.260Z
2015-12-11T19:53:50.260Z
vb le
<p>It's NP-complete for any number three or more of subgraphs.</p>

<p>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.</p>

<p>Here, $\times$ is the <a href="https://en.wikipedia.org/wiki/Tensor_product_of_graphs">tensor product of graphs</a>.
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}$.</p>

<p>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).</p>

<p>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.</p>

CC BY-SA 3.0
2015-12-11T19:38:53.737Z
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](http://renyi.mta.hu/~p_erdos/1976-23.pdf) 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
CC BY-SA 3.0
2015-12-11T03:27:39.590Z
2015-12-11T03:27:39.590Z
David Eppstein
<p>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?</p>

<reference-request><graph-theory><np-hardness><np-complete>
Partition graph into 2 or more claw-free subgraphs
Jaanus Käärmann
# Partition graph into 2 or more claw-free subgraphs

(Asked by: username_0 on 2015-12-11)

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?

**Tags:** reference-request, graph-theory, np-hardness, np-complete


---

## 2 answers

### Answer by username_1 on 2015-12-11. Score: 10

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](http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r46)),
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).


---

### Answer by username_2 on 2015-12-11. Score: 6

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](https://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: 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](http://renyi.mta.hu/~p_erdos/1976-23.pdf) 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.  

---

