A bound for the locating chromatic number of trees

Document Type: Research Paper

Authors

Imam Khomeini International University

Abstract

Let $f$ be a proper $k$-coloring of a connected graph $G$ and $\Pi=(V_1,V_2,\ldots,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),\ldots,d(v,V_k)),$ where $d(v,V_i)=\min\{d(v,x):~x\in V_i\}, 1\leq i\leq 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 $\chi_{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 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.

Keywords

Main Subjects


A. H. Assiyatun and E. T. Baskoro (2011). Locating-chromatic number of amalgamation of stars. ITB J. Sci.. 43A, 1-8
A. Behtoei and B. Omoomi, On the locating chromatic number of the cartesian product of graphs. to appear in Ars Combin..
A. Behtoei and B. Omoomi (2011). On the locating chromatic number of Kneser graphs. Discrete Appl. Math.. 159, 2214-2221
G. Chartrand, D. Erwin, M. A. Henning, P. J. Slater and P. Zhang (2002). The locating-chromatic number of a graph. Bull. Inst. Combin. Appl.. 36, 89-101
G. Chartrand, D. Erwin, M. A. Henning, P. J. Slater and P. Zhang (2003). Graphs of order n with locating-chromatic number n − 1. Discrete Math.. 269 (13), 65-79
G. Chartrand, F. Okamoto and P. Zhang (2009). The metric chromatic number of a graph. Australas. J. Combin.. 44, 273-286
G. Chartrand, V. Saenpholphat and P. Zhang (2005). Resolving edge colorings in graphs. Ars Combin.. 74, 33-47
G. Chartrand, E. Salehi and P. Zhang (2000). The partition dimension of a graph,. Aequationes Math.. 59 (1-2), 45-54
F. Harary and R. A. Melter (1976). On the metric dimension of a graph. Ars Combinatoria. 2, 191-195
V. Saenpholphat and P. Zhang Conditional resolvability in graphs: A survey. 2004 (37-40), 1997-2017