On locally-balanced 2-partitions of bipartite graphs

$2$-Разбиением графа $g$ называется функция $f:v(g)\rightarrow\{0,1\}$. $2$-Разбиение $f$ графа $g$ называется локально-сбалансированным с открытой окрестностью, если для любой вершины $v\in v(g),$ $\big||\{u\in n_g (v):f(u)=0\}|-|\{u\in n_g (v):f(u)=1\}|\big| \leq 1$. Двудольный граф называется $(a,b)$-бирегулярным, если все вершины одной доли имеют степень $a$, а все вершины другой доли имеют степень $b$. В настоящей работе доказано, что задача существo вания локально-сбалансированных $2$-разбиений с открытой окрестностью $np$-полна даже в случае $(3,8)$-бирегулярных двудольных графов. Также доказано, что $(2,2k+1)$-бирегулярный двудольный граф имеет локально-сбалансированное $2$-разбиение с открытой окрестностью тогда и только тогда, когда он не содержит простой цикл длины $2 (\mathrm{mod}~4)$. Кроме того, в работе доказано, что если субкубический двудольный граф $g$ не содержит простых циклов длины $2 (\mathrm{mod}~4)$, то он имеет локально-сбалансированное $2$-разбиение с открытой окрестностью. В конце работы показано, что все двояковыпуклые двудольные графы имеют локально-сбалансированное $2$-разбиение с открытой окрестностью.