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)|$$?
Partitioning finite directed graphs into 3 "incoming-sparse" sets
Dominic van der Zypen
- 48.9k
- 8
- 47
- 162