Return to Answer

This is NOW a complete answer. We can suppose that each color appears at most three times. Take the complement of the graph. Your question becomes equivalent to decide whether this graph has a perfect matching*, where we also allow triples (K_3) to be matched together. This problem WAS studied before:

Muse's answer gives a paper that has a reference to this paper that shows that this problem is in P, see the abstract or Lemma 1 and after:

P. Hell and D. G. Kirkpatrick: Packings by cliques and by finite families of graphs

Update: Ryan found an older paper proving the necessary result:

G. Cornuéjols, D. Hartvigsen, and W. Pulleyblank: Packing subgraphs in a graph

This is NOW a complete answer. We can suppose that each color appears at most three times. Take the complement of the graph. Your question becomes equivalent to decide whether this graph has a perfect matching*, where we also allow triples (K_3) to be matched together. This problem WAS studied before:

Muse's answer gives a paper that has a reference to this paper that shows that this problem is in P, see the abstract or Lemma 1 and after:

Hell, P.; Kirkpatrick, D. G., Packings by cliques and by finite families of graphs, Discrete Math. 49, 45–59 (1984). Zbl 0582.05046.

Update: Ryan found an older paper proving the necessary result:

Cornuéjols, G.; Hartvigsen, D.; Pulleyblank, W., Packing subgraphs in a graph, Oper. Res. Lett. 1, 139–143 (1982). Zbl 0488.90070.

This is NOW a complete answer. We can suppose that each color appears at most three times. Take the complement of the graph. Your question becomes equivalent to decide whether this graph has a perfect matching*, where we also allow triples (K_3) to be matched together. This problem WAS studied before:

Muse's answer gives a paper that has a reference to this paper that shows that this problem is in P, see the abstract or Lemma 1 and after:

P. Hell and D. G. Kirkpatrick: Packings by cliques and by finite families of graphs

This is NOW a complete answer. We can suppose that each color appears at most three times. Take the complement of the graph. Your question becomes equivalent to decide whether this graph has a perfect matching*, where we also allow triples (K_3) to be matched together. This problem WAS studied before:

Muse's answer gives a paper that has a reference to this paper that shows that this problem is in P, see the abstract or Lemma 1 and after:

P. Hell and D. G. Kirkpatrick: Packings by cliques and by finite families of graphs

Update: Ryan found an older paper proving the necessary result:

G. Cornuéjols, D. Hartvigsen, and W. Pulleyblank: Packing subgraphs in a graph

This is not a complete answer, but I think it can lead to a solution. We can suppose that each color appears at most three times. Take the complement of the graph. Your question becomes equivalent to decide whether this graph has a perfect matching*, where we also allow triples (K_3) to be matched together. This problem might have been studied before, but I guess that using the Gallai-Edmonds theorem it is not hard to show that it is in P. Or NP-complete...

This is NOW a complete answer. We can suppose that each color appears at most three times. Take the complement of the graph. Your question becomes equivalent to decide whether this graph has a perfect matching*, where we also allow triples (K_3) to be matched together. This problem WAS studied before:

Muse's answer gives a paper that has a reference to this paper that shows that this problem is in P, see the abstract or Lemma 1 and after:

P. Hell and D. G. Kirkpatrick: Packings by cliques and by finite families of graphs