Skip to main content
1 of 3

Partitioning finite directed graphs into 3 "incoming-sparse" sets

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 $v\in P_i$ we have $$|\text{In}(v)\cap P_i| < |\text{In}(v)\cap(V\setminus P_i)|$$?