Characterizing all trees with locating-chromatic number 3 - Edy Tri Baskoro; A Asmiati (Electronic Journal of Graph Theory and Applications (EJGTA), 2013)
Let $c$ be a proper $k$-coloring of a connected graph $G$. Let $Π = \{S_{1}, S_{2},…, 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_{Π}(v)$ of vertex $v$ is the ordered$k$-tuple $(d(v,S_{1}), d(v,S_{2}),…, d(v,S_{k}))$, where$d(v,S_{i})= \hbox{min}\{d(v,x)|x \in S_{i}\}$, for $1≤ i≤ 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 $χ_{L}(G)$, isthe smallest $k$ such that $G$ posses a locating $k$-coloring. Clearly, any graph of order $n ≥ 2$ have locating-chromatic number $k$, where $2 ≤ k ≤ 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.