A Bound for the Locating Chromatic Numbers of Trees

Abstract

Let $f$ be a proper $k$-coloring of a connected graph $G$ and $\Pi =(V_1,V_2,\dots ,V_k)$ 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 $\Pi$ is defined to be the ordered $k$-tuple $c_{{}_{\Pi }}(v)=(d(v,V_1),d(v,V_2),\dots ,d(v,V_k)),$ where $d(v,V_i)=\min \{d(v,x):x\in V_i\},1\le i\le 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 $\Cchi_{{}_L}(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 numbers 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.

9 pages, 3 figures

Cited by in corpus (1)

• The Neighbor-Locating-Chromatic Number of Pseudotrees