-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
    Apr 5, 2016 at 18:16
  • $\begingroup$ I wonder myself. $\endgroup$
    – Fedor Petrov
    Apr 5, 2016 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.