Skip to main content
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
added 13 characters in body
Source Link

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)|$$?

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

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)|$$?

added 70 characters in body
Source Link

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

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)|$$?

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

Source Link

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)|$$?