The neighbor-locating-chromatic number of trees and unicyclic graphs

Abstract

A k-coloring of a graph is neighbor-locating if any two vertices with the same color can be distinguished by the colors of their respective neighbors, that is, the sets of colors of their neighborhoods are different. The neighbor- locating chromatic number χNL(G) is the minimum k such that a neighbor- locating k-coloring of G exists. In this paper, we give upper and lower bounds on the neighbor-locating chromatic number in terms of the order and the degree of the vertices for unicyclic graphs and trees. We also obtain tight upper bounds on the order of trees and unicyclic graphs in terms of the neighbor-locating chromatic number. Further partial results for trees are also established.