×

On locally-balanced 2-partitions of bipartite graphs. (English) Zbl 1493.05245

Summary: 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 \pmod 4\). Next, we prove that if \(G\) is a subcubic bipartite graph that has no cycle of length \(2 \pmod 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.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q25 Analysis of algorithms and problem complexity

References:

[1] G. Chartrand, P. Zhang, Chromatic Graph Theory, Discrete Mathematics and its Applications, CRC Press, 2009 · Zbl 1169.05001 · doi:10.1201/9781584888017
[2] D. B. West, Introduction to Graph Theory, Prentice-Hall, N.J., 2001
[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:10.1145/1007912.1007931
[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
[5] C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973 · Zbl 0254.05101
[6] A. Ghouila-Houri, “Caractérisation des matrices totalement unimodulaires”, C. R. Acad. Sci. (Paris), 254:7 (1962), 1192-1194 · Zbl 0114.25102
[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
[8] W. Meyer, “Equitable Coloring”, American Mathematical Monthly, 80:8 (1973), 920-922 · Zbl 0279.05106 · doi:10.2307/2319405
[9] A. V. Kostochka, “Equitable Colorings of Outerplanar Graphs”, Discrete Mathematics, 258 (2002), 373-377 · Zbl 1009.05059 · doi:10.1016/S0012-365X(02)00538-1
[10] D. de Werra, “On Good and Equitable Colorings”, Cahiers du C.E.R.O., 17 (1975), 417-426 · Zbl 0331.05107
[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 · Zbl 1020.05028 · doi:10.1016/S0095-8956(02)00035-7
[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 · Zbl 0965.90053 · doi:10.1016/S0377-2217(99)00459-2
[14] C. Bazgan, Zs. Tuza, D. Vanderpooten, “The Satisfactory Partition Problem”, Discrete Applied Mathematics, 154 (2006), 1236-1245 · Zbl 1095.68073 · doi:10.1016/j.dam.2005.10.014
[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
[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
[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 · Zbl 1493.05244 · doi:10.46991/PYSU:A/2020.54.1.009
[21] W. T. Tutte, “The Subgraph Problem”, Ann. Discrete Math., 3 (1978), 289-295 · Zbl 0377.05034 · doi:10.1016/S0167-5060(08)70514-4
[22] A. Darmann, J. Döcker, “On a Simple Hard Variant of Not-All-Equal 3-Sat”, Theoretical Computer Science, 815 (2020), 147-152 · Zbl 1433.68272 · doi:10.1016/j.tcs.2020.02.010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.