Characterizing all trees with locating-chromatic number 3

Let c be a proper k-coloring of a connected graph G. Let Π = {S1, S2, ... , Sk} be the induced partition of V (G) by c, where Si is the partition class having all vertices with color i. The color code cΠ(v) of vertex v is the ordered k-tuple (d(v, S1); d(v, S2), ... , d(v, Sk)), where d(v, Si) = min{d(v, x)|x in Si}, for 1 ≤ i ≤ k. If all vertices of G have distinct color codes, then c is called a locating-coloring of G. The locating-chromatic number of G, denoted by L(G), is the smallest k such that G posses a locating k-coloring. Clearly, any graph of order n ≥ 2 has locating-chromatic number k, where 2 ≤ k ≤ n. Characterizing all graphs with a certain locating-chromatic number is a difficult problem. Up to now, all graphs of order n with locating chromatic number 2, n - 1, or n have been characterized. In this paper, we characterize all trees whose locating-chromatic number is 3. We also give a family of trees with locating-chromatic number 4.