Disseminating quality controlled scientific knowledge

# Characterizing all trees with locating-chromatic number 3

Author(s): Edy Tri Baskoro | A Asmiati

Journal: Electronic Journal of Graph Theory and Applications
ISSN 2338-2287

Volume: 1;
Issue: 2;
Date: 2013;
Original page

Keywords: Locating-chromatic number | graph | tree

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 \$1leq ileq 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. 