Let $G=(V,E)$ be a directed graph. For $v\in V$ set $\text{In}(v)=\{x\in V: (x,v)\in E\}$. 


Is it possible to find a partition $P\_1,P\_2,P\_3$ of $V$ such that for every $P\_i$ and every vertex $v\in P\_i$ we have $$|\text{In}(v)\cap P\_i| \leq |\text{In}(v)\cap(V\setminus P\_i)|$$?



Partitioning finite directed graphs into 3 "incoming-sparse" sets
Suppose you have a edge (A,B), and B has at most two incoming edges. Then A and B must get different colors in order for the inequality to be preserved. Now have C get an edge from each of A and B. With no other incoming edges to C or B, this "mini-tournament" must get three colors.


Now add D, E, F so that B and C lead to D, C and D to E, D and E to F. With no other edges involved, we get a repeated coloring with A and D getting the same color, as do B and E, and C and F.


Now have the snake come and bite its own tail. Make a bracelet of these vertices. If we have the number of vertices be a multiple of 3, then a coloring exists. Otherwise not.


Gerhard "Or Oroubourous Or Orrery Or..." Paseman, 2016.04.02.


