LOCALLY-BALANCED k-PARTITIONS OF GRAPHS Petros Petrosyan
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 v∈V(G) and any 0≤i<j≤k−1||{u∈NG(v):f(u)=i}|−|{u∈NG(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 v∈V(G) and any 0≤i<j≤k−1||{u∈NG[v]:f′(u)=i}|−|{u∈NG[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.
DOI: 10.46991/PYSU:A/2021.55.2.096 Physical and Mathematical Sciences, 55(2 (255) 96-112
