It'll be great to get a pointer or answer to the following question:
What is the complexity of the following problem? Given an unweighted and undirected graph, can we have a proper (not necessarily minimal) vertex coloring of the graph in which each color is used at least twice?
