Geodesic
On locally-balanced $2$-partitions of some classes of graphs
Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 54 (2020) no. 1, pp. 9-19.

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

In this paper we obtain some conditions for the existence of locally-balanced $2$-partitions with an open (with a closed) neighborhood of some classes of graphs. In particular, we give necessary conditions for the existence of locally-balanced $2$-partitions of even and odd graphs. We also obtain some results on the existence of locally-balanced $2$-partitions of rook's graphs and powers of cycles. In particular, we prove that if $m,n\geq 2$, then the graph $K_{m} \Box K_{n}$ has a locally-balanced $2$-partition with a closed neighborhood if and only if $m$ and $n$ are even. Moreover, all our proofs are constructive and provide polynomial time algorithms for constructing the required $2$-partitions.
Keywords: locally-balanced $2$-partition, equitable coloring, even (odd) graph, rook's graph, power of cycles. 
@article{UZERU_2020_54_1_a1,
     author = {A. G. Gharibyan},
     title = {On locally-balanced $2$-partitions of some classes of graphs},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {9--19},
     publisher = {mathdoc},
     volume = {54},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2020_54_1_a1/}
}
TY  - JOUR
AU  - A. G. Gharibyan
TI  - On locally-balanced $2$-partitions of some classes of graphs
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2020
SP  - 9
EP  - 19
VL  - 54
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZERU_2020_54_1_a1/
LA  - en
ID  - UZERU_2020_54_1_a1
ER  - 
%0 Journal Article
%A A. G. Gharibyan
%T On locally-balanced $2$-partitions of some classes of graphs
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2020
%P 9-19
%V 54
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZERU_2020_54_1_a1/
%G en
%F UZERU_2020_54_1_a1
A. G. Gharibyan. On locally-balanced $2$-partitions of some classes of graphs. Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 54 (2020) no. 1, pp. 9-19. http://geodesic.mathdoc.fr/item/UZERU_2020_54_1_a1/

[1] G. Chartrand, P. Zhang, Chromatic Graph Theory, Chapman Hall/CRC Press, 2008 | MR | Zbl

[2] D. B. West, Introduction to Graph Theory, Prentice-Hall, New Delhi, 2003 | MR | Zbl

[3] 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

[4] C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd., 1985 | MR

[5] A. Hajnal, E. Szemerédi, “Proof of a Conjecture of P. Erdős”, Combinatorial Theory and Its Applications, North-Holland, Amsterdam, 1970, 601–623 | MR | Zbl

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

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

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

[9] J. Kratochvil, “Complexity of Hypergraph Coloring and Seidel’s Switching”, Graph Theoretic Concepts in Computer Science, 29th International Workshop, Lecture Notes in Comput. Sci., 2880, Elspeet, The Netherlands, 2003, 297–308 | MR | Zbl

[10] 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

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

[12] 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

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

[14] A. H. Gharibyan, P. A. Petrosyan, “On Locally-balanced 2-partitions of Grid-like Graphs”, International Conference on Mathematics, Informatics and Information Technologies Dedicated to the Illustrious Scientist Valentin Belousov MITI 2018, Alecu Russo Balti State University, Republic of Moldova, Balti, 2018, 111–112 | MR