Skip to main content
MathOverflow

Return to Question

replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link
Community Bot
Community Bot
  • 1
  • 2
  • 3

(A version of this questionthis question for undirected graphs.)

Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ set $$ N(v) := \{x\in V: \{x,v\}\in E\}. $$ Is it possible to find a partition $P_1,P_2$ of $V$ such that for every $P_i$ and $v\in P_i$ we have $$|N(v)\cap P_i| \leq |N(v)\cap(V\setminus P_i)|$$?

(A version of this question for undirected graphs.)

Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ set $$ N(v) := \{x\in V: \{x,v\}\in E\}. $$ Is it possible to find a partition $P_1,P_2$ of $V$ such that for every $P_i$ and $v\in P_i$ we have $$|N(v)\cap P_i| \leq |N(v)\cap(V\setminus P_i)|$$?

(A version of this question for undirected graphs.)

Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ set $$ N(v) := \{x\in V: \{x,v\}\in E\}. $$ Is it possible to find a partition $P_1,P_2$ of $V$ such that for every $P_i$ and $v\in P_i$ we have $$|N(v)\cap P_i| \leq |N(v)\cap(V\setminus P_i)|$$?

Added top-level tag.
Source Link
Stefan Kohl ♦
Stefan Kohl ♦
  • 19.6k
  • 21
  • 75
  • 137

(A version of this question for undirected graphs.)

Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ set $N(v)=\{x\in V: \{x,v\}\in E\}$.

Is $$ N(v) := \{x\in V: \{x,v\}\in E\}. $$ Is it possible to find a partition $P_1,P_2$ of $V$ such that for every $P_i$ and $v\in P_i$ we have $$|N(v)\cap P_i| \leq |N(v)\cap(V\setminus P_i)|$$?

(A version of this question for undirected graphs.)

Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ set $N(v)=\{x\in V: \{x,v\}\in E\}$.

Is it possible to find a partition $P_1,P_2$ of $V$ such that for every $P_i$ and $v\in P_i$ we have $$|N(v)\cap P_i| \leq |N(v)\cap(V\setminus P_i)|$$?

(A version of this question for undirected graphs.)

Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ set $$ N(v) := \{x\in V: \{x,v\}\in E\}. $$ Is it possible to find a partition $P_1,P_2$ of $V$ such that for every $P_i$ and $v\in P_i$ we have $$|N(v)\cap P_i| \leq |N(v)\cap(V\setminus P_i)|$$?

Source Link
Dominic van der Zypen
Dominic van der Zypen
  • 48.9k
  • 8
  • 47
  • 162

Splitting the vertices of undirected graphs into 2 sparse sets

(A version of this question for undirected graphs.)

Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ set $N(v)=\{x\in V: \{x,v\}\in E\}$.

Is it possible to find a partition $P_1,P_2$ of $V$ such that for every $P_i$ and $v\in P_i$ we have $$|N(v)\cap P_i| \leq |N(v)\cap(V\setminus P_i)|$$?