show/hide this revision's text 3 added 378 characters in body; added 54 characters in body

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
show/hide this revision's text 2 added 456 characters in body; deleted 147 characters in body; added 39 characters in body

This is not NOW 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 WAS studied before, but I guess :

Muse's answer gives a paper that using the Gallai-Edmonds theorem it is not hard has a reference to show this paper that it shows that this problem is in P, see the abstract or Lemma 1 and after:

P. Or NP-complete..Hell and D. G. Kirkpatrick: Packings by cliques and by finite families of graphs
show/hide this revision's text 1

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