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?

$\endgroup$

1 Answer 1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.