Tight Bounds for the N₂-Chromatic Number of Graphs

Let G be a connected graph. A vertex coloring of G is an N₂-vertex coloring if, for every vertex v, the number of different colors assigned to the vertices adjacent to v is at most two. The N₂-chromatic number of G is the maximum number of colors that can be used in an N₂-vertex coloring of G. In this paper, we establish tight bounds for the N₂-chromatic number of a graph in terms of its maximum degree and its diameter, and characterize those graphs that attain these bounds.