Characterizing All Trees with Locating-chromatic Number 3
2013
Edy Tri Baskoro, A. Asmiati

Metrics

  • Eye Icon 193 views
  • Download Icon 73 downloads
Metrics Icon 193 views  //  73 downloads
Characterizing All Trees with Locating\u002Dchromatic Number 3 Image
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 $1\leq i\leq 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.

Full text
Show more arrow
 
More from this journal
Computation of Gutman Index of Some Cactus Chains
Computation of Gutman Index of Some Cactus Chains Image
On Topological Integer Additive Set-labeling of Star Graphs
On Topological Integer Additive Set\u002Dlabeling of Star Graphs Image
🧐  Browse all from this journal

Metrics

  • Eye Icon 193 views
  • Download Icon 73 downloads
Metrics Icon 193 views  //  73 downloads