This question is inspired by problem 1 of the combinatorics test of the 2012 third round iranian olympiad which is as follows:


We've colored edges of $K\_n$ with $n-1$ colors. We call a vertex rainbow if it's connected to all of the colors. At most how many rainbows can exist?


How can we find the maximum number of rainbows for an arbitrary simple finite graph $G$ on $c$ colors?



How to calculate the maximum number of rainbows for arbitrary graphs?
For arbitrary graphs, the problem is NP-complete. It includes as a special case the problem of coloring the edges of a 3-regular graph with three colors, so that each vertex is rainbow, which was shown NP-complete by Ian Holyer, The NP-completeness of edge-colouring, SIAM J. Comput. 1981.


