ON THE PACKING k-COLORING OF SOME FAMILY TREES

Abstract

All graphs in this paper are simple and connected. Let $G=(V,E)$ be a graph where $V(G)$ is nonempty of vertex set of $G$ and $E(G)$ is possibly empty set of unordered pairs of elements of $V(G)$. The distance from $u$ to $v$ in $G$ is the length of a shortest path joining them, denoted by $d(u,v)$. For some positive integer $k$, a function $ c:V(G)\rightarrow \{1,2,...k\} $ is called packing $k-$coloring if any two not adjacent vertices $u$ and $v$, $c(u)=c(v)=i$ and $d(u,v)\geq i+1$. The minimum number $k$ such that the graph $G$ has a packing $k-$coloring is called the packing chromatic number, denoted by $\chi_\rho(G) $. In this paper, we investigate the packing chromatic number of some family trees, namely centipede, firecracker, broom, double star and banana tree graphs.