Geodesic
On locally-balanced 2-partitions of bipartite graphs
Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 54 (2020) no. 3, pp. 137-145.

Voir la notice de l'article provenant de la source Math-Net.Ru

A $2$-partition of a graph $G$ is a function $f:V(G)\rightarrow \{0,1\}$. A $2$-partition $f$ of a graph $G$ is a locally-balanced with an open neighborhood, if for every $v\in V(G)$, $\left\vert \vert \{u\in N_{G}(v)\colon\,f(u)=0\}\vert-\vert\{u\in N_{G}(v)\colon\,f(u)=1\}\vert \right\vert\leq 1$. A bipartite graph is $(a,b)$-biregular, if all vertices in one part have degree a and all vertices in the other part have degree $b$. In this paper we prove that the problem of deciding, if a given graph has a locally-balanced 2-partition with an open neighborhood is NP-complete even for $(3, 8)$-biregular bipartite graphs. We also prove that a $(2,2k+1)$-biregular bipartite graph has a locally-balanced $2$-partition with an open neighbourhood if and only if it has no cycle of length $2 (\mathrm{mod}~4)$. Next, we prove that if $G$ is a subcubic bipartite graph that has no cycle of length $2 (\mathrm{mod}~4)$, then $G$ has a locally-balanced $2$-partition with an open neighbourhood. Finally, we show that all doubly convex bipartite graphs have a locally-balanced $2$-partition with an open neighbourhood.
Keywords: locally-balanced $2$-partition, NP-completeness, biregular bipartite graph, subcubic bipartite graph.
Mots-clés : bipartite graph 
@article{UZERU_2020_54_3_a1,
     author = {A. H. Gharibyan and P. A. Petrosyan},
     title = {On locally-balanced 2-partitions of bipartite graphs},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {137--145},
     publisher = {mathdoc},
     volume = {54},
     number = {3},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2020_54_3_a1/}
}
TY  - JOUR
AU  - A. H. Gharibyan
AU  - P. A. Petrosyan
TI  - On locally-balanced 2-partitions of bipartite graphs
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2020
SP  - 137
EP  - 145
VL  - 54
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZERU_2020_54_3_a1/
LA  - en
ID  - UZERU_2020_54_3_a1
ER  - 
%0 Journal Article
%A A. H. Gharibyan
%A P. A. Petrosyan
%T On locally-balanced 2-partitions of bipartite graphs
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2020
%P 137-145
%V 54
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZERU_2020_54_3_a1/
%G en
%F UZERU_2020_54_3_a1
A. H. Gharibyan; P. A. Petrosyan. On locally-balanced 2-partitions of bipartite graphs. Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 54 (2020) no. 3, pp. 137-145. http://geodesic.mathdoc.fr/item/UZERU_2020_54_3_a1/

[1] G. Chartrand, P. Zhang, Chromatic Graph Theory, Discrete Mathematics and its Applications, CRC Press, 2009 | DOI | MR

[2] D. B. West, Introduction to Graph Theory, Prentice-Hall, N.J., 2001 | MR

[3] K. Andreev, H. Räcke, Balanced Graph Partitioning (Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures), Barcelona, Spain, 120–124 | DOI

[4] S. V. Balikyan, R. R. Kamalian, “On NP-Completeness of the Problem of Existence of Locally-balanced 2-partition for Bipartite Graphs $G$ with $D(G) = 3$”, Doklady NAN RA, 105:1 (2005), 21–27 | MR

[5] C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973 | MR | Zbl

[6] A. Ghouila-Houri, “Caractérisation des matrices totalement unimodulaires”, C. R. Acad. Sci. (Paris), 254:7 (1962), 1192–1194 | MR | Zbl

[7] A. Hajnal, E. Szemeredi, “Proof of a conjecture of P. Erdős”, Combinatorial Theory and Its Applications, v. 2, North-Holland, London, 1969, 601–623 | MR

[8] W. Meyer, “Equitable Coloring”, American Mathematical Monthly, 80:8 (1973), 920–922 | DOI | MR | Zbl

[9] A. V. Kostochka, “Equitable Colorings of Outerplanar Graphs”, Discrete Mathematics, 258 (2002), 373–377 | DOI | MR | Zbl

[10] D. de Werra, “On Good and Equitable Colorings”, Cahiers du C.E.R.O., 17 (1975), 417–426 | MR

[11] A. V. Kostochka, M. Stiebitz, “A New Lower Bound on the Number of Edges in Colour-Critical Graphs and Hypergraphs”, J. Combin. Theory. Ser. B., 87:2 (2003), 374–402 | DOI | MR | Zbl

[12] M. Gerber, D. Kobler, Partitioning a Graph to Satisfy all Vertices, Technical Report, Swiss Federal Institute of Technology, Lausanne, 1998

[13] M. Gerber, D. Kobler, “Algorithmic Approach to the Satisfactory Graph Partitioning Problem”, European J. Oper. Res., 125 (2000), 283–291 | DOI | MR | Zbl

[14] C. Bazgan, Zs. Tuza, D. Vanderpooten, “The Satisfactory Partition Problem”, Discrete Applied Mathematics, 154 (2006), 1236–1245 | DOI | MR | Zbl

[15] S. V. Balikyan, R. R. Kamalian, “On NP-completeness of the Problem of Existence of Locally-balanced 2-partition for Bipartite Graphs $G$ with $D(G) = 4$ under the Extended Definition of the Neighbourhood of a Vertex”, Doklady NAN RA, 106:3 (2006), 218–226 | MR

[16] S. V. Balikyan, “On Existence of Certain Locally-balanced 2-partition of a Tree”, Mathematical Problems of Computer Science, 30 (2008), 25–30

[17] S. V. Balikyan, R. R. Kamalian, “On Existence of 2-partition of a Tree, which Obeys the Given Priority”, Mathematical Problems of Computer Science, 30 (2008), 31–35

[18] S. V. Balikyan, On Locally-balanced 2-partition of Some Bipartite Graphs (Proceedings of the XV International Conference “Mathematics. Computing. Education”), Barc Dubna, Russia, 2008, 13 pp.

[19] A. H. Gharibyan, P. A. Petrosyan, “Locally-balanced 2-partitions of Complete Multipartite Graphs”, Mathematical Problems of Computer Science, 49 (2018), 7–17 | MR

[20] A. G. Gharibyan, “On Locally-balanced 2-Partitions of Some Classes of Graphs”, Proceedings of the YSU, Physical and Mathematical Sciences, 54:1 (2020), 9–19 | DOI | MR

[21] W. T. Tutte, “The Subgraph Problem”, Ann. Discrete Math., 3 (1978), 289–295 | DOI | MR | Zbl

[22] A. Darmann, J. Döcker, “On a Simple Hard Variant of Not-All-Equal 3-Sat”, Theoretical Computer Science, 815 (2020), 147–152 | DOI | MR | Zbl