Locally-balanced $k$-partitions of graphs

A. H. Gharibyan ; P. A. Petrosyan

Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 55 (2021) no. 2, pp. 96-112.

Résumé

In this paper we generalize locally-balanced $2$-partitions of graphs and introduce a new notion, the locally-balanced $k$-partitions of graphs, defined as follows: a $k$-partition of a graph $G$ is a surjection $f:V(G)\rightarrow \{0,1,\ldots,k-1\}$. A $k$-partition ($k\geq 2$) $f$ of a graph $G$ is a locally-balanced with an open neighborhood, if for every $v\in V(G)$ and any $0\leq i$ $$\left\vert \vert \{u\in N_{G}(v)\colon\,f(u)=i\}\vert - \vert \{u\in N_{G}(v)\colon\,f(u)=j\}\vert \right\vert\leq 1.$$ A $k$-partition ($k\geq 2$) $f^{\prime}$ of a graph $G$ is a locally-balanced with a closed neighborhood, if for every $v\in V(G)$ and any $0\leq i$ $$\left\vert \vert \{u\in N_{G}[v]\colon\,f^{\prime}(u)=i\}\vert - \vert \{u\in N_{G}[v]\colon\,f^{\prime}(u)=j\}\vert \right\vert\leq 1.$$ The minimum number $k$ ($k\geq 2$), for which a graph $G$ has a locally-balanced $k$-partition with an open (a closed) neighborhood, is called an $lb$-open ($lb$-closed) chromatic number of $G$ and denoted by $\chi_{(lb)}(G)$ ($\chi_{[lb]}(G)$). In this paper we determine or bound the $lb$-open and $lb$-closed chromatic numbers of several families of graphs. We also consider the connections of $lb$-open and $lb$-closed chromatic numbers of graphs with other chromatic numbers such as injective and $2$-distance chromatic numbers.

Bibliographie

[1] A. S. Asratian, T. M. J. Denley, R. Haggkvist, Bipartite graphs and their applications, Cambridge Tracts in Mathematics, 131, Cambridge University Press, 1998 | MR | Zbl

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

[3] K. Andreev, H. Räcke, “Balanced graph partitioning”, Proc. sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, Barcelona, Spain, 2004, 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 (in Russian) | 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] 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 | 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] A. H. Gharibyan, P. A. Petrosyan, “Locally-balanced 2-Partitions of Complete Multipartite Graphs”, Mathematical Problems of Computer Science, 49 (2018), 7–17 | DOI | MR

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

[20] A. H. Gharibyan, P. A. Petrosyan, “On Locally-balanced $2$-Partitions of Bipartite Graphs”, Proceedings of the YSU, Physical and Mathematical Sciences, 54:3 (2020), 137–145 | DOI

[21] S. V. Balikyan, On Locally-balanced $2$-Partitions of Graphs, PhD Thesis, YSU Press, Yer., 2008, 104 pp. (in Russian)

[22] G. Hahn, J. Kratochvíl, J. Širáň, D. Sotteau, “On the Injective Chromatic Number of Graphs”, Discrete Math., 256:1–2 (2002), 179–192 | DOI | MR | Zbl

[23] F. Kramer, H. Kramer, “Un Probleme de Coloration des Sommets d’un Graphe”, C.R. Acad. Sci. A, 268 (1969), 46–48 | Zbl

[24] F. Kramer, H. Kramer, “A Survey on the Distance-coloring of Graphs”, Discrete Math., 308:2-3 (2008), 422–426 | DOI | Zbl