Sharp Bounds and Precise Values for the Ni-Chromatic Number of Graphs

Let G be a connected undirected graph. A vertex coloring f of G is an N-i-vertex coloring if for each vertex x in G, the number of different colors assigned to N-G(x) is at most i. The N-i-chromatic number of G, denoted by t(i)(G), is the maximum number of colors which are used in an N-i-vertex coloring of G. In this paper, we provide sharp bounds for t(i)(G) of a graph G in terms of its vertex cover number, maximum degree and diameter, respectively. We also determine precise values for t(i)(G) in some cases.