1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .