LOCALLY-BALANCED k-PARTITIONS OF GRAPHS - Gharibyan, Aram H.; Petrosyan, Petros A. (Proceedings of the YSU A: Physical and Mathematical Sciences, 2021)
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)→ {0,1,…,k-1}. A k-partition (k≥ 2) f of a graph G is a locally-balanced with an open neighborhood, if for every vV(G) and any 0≤ i<j≤ k-1 {uN_G(v)f(u)=i}- {uN_G(v)f(u)=j}≤ 1. A k-partition (k≥ 2) f^′ of a graph G is a locally-balanced with a closed neighborhood, if for every vV(G) and any 0≤ i<j≤ k-1 {uN_G[v]f^′(u)=i}- {uN_G[v]f^′(u)=j}≤ 1. The minimum number k (k≥ 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 χ_(lb)(G) (χ_[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.