On Locally-balancad 2-partitions of Some Bipartite Graphs
Balikyan S.V.
"Математика. Компьютер. Образование". Cб. трудов XV международной конференции. Под общей редакцией Г.Ю. Ризниченко Ижевск: Научно-издательский центр "Регулярная и хаотическая динамика", 2008. Vol. 2, 276pp. Pp. 17-29. (accepted)
Necessary and sufficient condition is obtained for the problem of such partitioning of the set of vertices of a bipartite graph G, in which arbitrary two simple cycles have at most one common vertex, into two disjoint subsets V1 and V2, which satisfies the condition ||λ(v)∩V1|‒|λ(v)∩V2|| ≤ 1 for any vertex v of G, where λ(v) is the set of all vertices of G adjacent to v.
|