A bound for the locating chromatic number of trees

Let f be a proper k-coloring of a connected graph G and Π = (V1, V2, . . . , Vk ) be an ordered partition of V (G) into the resulting color classes. For a vertex v of G, the color code of v with respect to Π is defined to be the ordered k-tuple cΠ (v) = (d(v, V1), d(v, V2), . . . , d(v, Vk )), where d(v, Vi) = min{d(v, x) : x ∈ Vi}, 1 ≤ i ≤ k. If distinct vertices have distinct color codes, then f is called a locating coloring. The minimum number of colors needed in a locating coloring of G is the locating chromatic number of G, denoted by χ (G). In this paper, we study the locating chromatic numbers of trees. We provide a counter example to a theorem of Gary Chartrand et al. [G. Chartrand,D. Erwin, M.A. Henning, P.J. Slater, P. Zhang, The locating-chromatic number of a graph, Bull. Inst. Combin. Appl. 36 (2002) 89-101] about the locating chromatic number of trees. Also, we offer a new bound for the locating chromatic number of trees. Then, by constructing a special family of trees, we show that this bound is best possible.