-2
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Yes, it is a variant of Lovasz partition lemma. Choose partition $V=P_1\sqcup P_2$ for which the number $E(G|_{P_1})+E(G|_{P_2})$of edges which join vertices of the same part is minimal possible. It works for each vertex $v$: else moving $v$ to other part decreases this value.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks Fedor--is there a variant of this lemma for directed graphs? $\endgroup$
    – Dominic van der Zypen
    Commented Apr 5, 2016 at 18:16
  • $\begingroup$ I wonder myself. $\endgroup$
    – Fedor Petrov
    Commented Apr 5, 2016 at 18:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .