Academic Journals Database
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

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.
RPA Switzerland

Robotic Process Automation Switzerland


Tango Jona
Tangokurs Rapperswil-Jona