Characterizing all trees with locating-chromatic number 3

Abstract

Let $c$ be a proper $k$-coloring of a connected graph $G$.  Let $\Pi = \{S_{1}, S_{2},\ldots, S_{k}\}$ be the induced  partition of $V(G)$ by $c$,  where $S_{i}$ is the partition class having all vertices with color $i$.The color code $c_{\Pi}(v)$ of vertex $v$ is the ordered$k$-tuple $(d(v,S_{1}), d(v,S_{2}),\ldots, d(v,S_{k}))$, where$d(v,S_{i})= \hbox{min}\{d(v,x)|x \in S_{i}\}$, for $1\leq i\leq k$.If all vertices of $G$ have distinct color codes, then $c$ iscalled a locating-coloring of $G$.The locating-chromatic number of $G$, denoted by $\chi_{L}(G)$, isthe smallest $k$ such that $G$ posses a locating $k$-coloring. Clearly, any graph of order $n \geq 2$ have locating-chromatic number $k$, where $2 \leq k \leq n$. Characterizing all graphswith a certain locating-chromatic number is a difficult problem. Up to now, we have known allgraphs of order $n$ with locating chromatic number $2, n-1,$ or $n$.In this paper, we characterize all trees whose locating-chromatic number $3$. We also give a family of trees with locating-chromatic number 4.