Let $G$ be a graph with $n$ vertices and let $r$ be a number dividing $n$. We say that $G$ is strongly $r$-colorable if for every partition of the vertices of $G$ into sets of size $r$, there exists a proper coloring of $G$ in which every set in the partition is colored in all colors. Alon was the first who showed that if $r>cd$ then $G$ must be strongly $r$-colorable, where $d$ is the maximum degree in the graph and $c$ is some constant number. This result raises the question, for a fixed number $d$, what is the minimum number $s(d)$ with the property that every graph with maximum degree $d$ is strongly $s(d)$-colorable? It is not hard to show that $s(d)$ is at least $2d$ and the natural conjecture is $s(d)=2d$. The result closest to this conjecture is Haxell's proof that $s(d) \leq 11d/4+o(d)$. In this talk I will describe the arsenal of methods used to attack this problem and show that $s(2) = 4$. This is joint work with Abeer Shkerat.