Abstract

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.

‹ 1 / ? › − 100% + Open in new tab Download Cite

Loading the full text…