We prove by induction on $n$, the number of vertices in the graph. When $n = 3$ the result clearly holds (place each vertex in its own set), so we suppose the statement holds for some $n = N \ge 3$. Consider a digraph $G$ on $N + 1$ vertices where each vertex has out-degree $2$. By PHP, unless every vertex of $G$ has in-degree exactly equal to $2$, some vertex $v_0$ of $G$ has in-degree at most $1$. Consider the graph $G'$ we obtain by removing $v_0$ and the associated edges from $G$; $G'$ is a digraph on $N$ vertices where each vertex has out-degree at most $2$. By the induction hypothesis ("at most" is weaker than "exactly", so we can apply the inductive hypothesis directly), the vertices of $G'$ can be partitioned into $3$ sets such that no vertex $v$ is in the same set as both vertices it points to. We claim we can make a valid placement of $v_0$ into one of these sets. Indeed, if it's impossible to place $v_0$ in a set, either both vertices that $v_0$ points to are in that set, or one of the vertices pointing to $v_0$ (and all the other vertices that vertex points to) are in the set. The first case rules out at most one of the three sets, and since the in-degree of $v_0$ is at most $1$, the second case rules out at most one set. Hence it's possible to place $v_0$ in one of these sets such that the problem condition holds. Otherwise, every vertex has in and out-degree exactly $2$. Choose an arbitrary vertex $v_0$. Suppose it points to $v_a$ and $v_b$, and is pointed to by $v_1$ and $v_2$. Let $v'$ be the other vertex pointing to $v_a$. Finally, let $v_1'$ and $v_2'$ be the other vertices that $v_1, v_2$ point to, respectively. Consider the graph $G'$ we obtain by removing $v_0$ and the associated edges from $G$ and subsequently drawing the edges from $v_1$ and $v_2$ to $v'$ (now utilizing the full strength of the induction hypothesis). Every vertex of $G'$ has out-degree $2$, so by hypothesis the vertices of $G'$ can be partitioned into $3$ sets $S_1, S_2, S_3$ such that no vertex $v$ is in the same set as both vertices it points to. We can make a valid placement of $v_0$ in one of these sets unless (WLOG), $v_1, v_1' \in S_1$, $v_2, v_2' \in S_2$, and $v_a, v_b \in S_3$. Now remark $v' \not \in S_1, S_2$ since otherwise either $v_1$ or $v_2$ would be in the same set as the two vertices it points to. Then $v' \in S_3$. Now at least one of $S_1, S_2$ does not contain both vertices that $v_a$ points to; we can move $v_a$ from $S_3$ to this set (WLOG $S_1$) and maintain the validity of the partition since neither of the two vertices that point to $v_a$ (namely, $v$ and $v'$) are in this set. Finally, place $v$ in $S_3$; then $v_1$, $v_2$, $v_a$ are all in a different set from $v$ and we're done.

hyperbolictangent wrote: Otherwise, every vertex has in and out-degree exactly $2$. Choose an arbitrary vertex $v_0$. Suppose it points to $v_a$ and $v_b$, and is pointed to by $v_1$ and $v_2$. Let $v'$ be the other vertex pointing to $v_a$. Finally, let $v_1'$ and $v_2'$ be the other vertices that $v_1, v_2$ point to, respectively. Here's a more conceptual approach (IMO): Take a partition that maximizes the number of (good) edges between distinct sets. If some $v$ belongs to the same set as its out-neighbors, moving $v$ to one of the other two sets (whichever has fewer in-neighbors of $v$) will add 2 good edges but kill at most 1 old one, which is impossible.

Sorry, the argument is not clear to me. Suppose we have edges $av$, $bv$, $cv$, $dv$, $ev$, $fv$, $vx$, $vy$ (among possibly others) and the initial partition is $\{a, b, c, \ldots\}$, $\{d, e, f, \ldots\}$, $\{v, x, y, \ldots\}$. Moving $v$ to either of the other groups creates 2 and kills 3 good edges. Why can't this be the maximal partition? Edit: response via PM: math154 wrote: $v$ has in-degree greater than 2 here; I was just mentioning an alternative approach to the case in which all in-degrees and out-degrees are 2. Aha, I see, I missed that you were working in that special case. Objection withdrawn.

Huh, is it just me or is all this rather overcomplicated? We could just delete one of the edges coming from every vertex; we end up with a graph with a bunch of connected components, each with exactly one (directed) cycle, and this is easy to 3-color. Just start by coloring the cycle (e.g. either 1212...12 or 1212...123 by parity) and iteratively pick a color for each remaining vertex that's different from the vertex it points to.

It IS overcomplicated. Delete one outedge from every vertex, we claim that the resulting subgraph can be $3-coloured$: either it is the union of several vertex-disjoint cycles, or it has at least one vertex with indegree $0$. The former is obvious and the latter is trivial by induction. QED