Packing Chromatic Number of Circular Fans and Mesh of Trees
Albert William, S. Roy, Indra Rajasingh · International Journal of Mathematics and Soft Computing · 2014
The packing chromatic number $\raisebox{2pt}{$\chi$}_{\rho}(G)$ of a graph $G$ is the smallest integer $k$ for which there exists a mapping $\pi:V(G)\longrightarrow \{1,2,...,k\}$ such that any two vertices of color $i$ are at distance at least $i+1$. It is a frequency assignment problem used in wireless networks, which is also called broadcast coloring. It is proved that packing coloring is NP-complete for general graphs and even for trees. In this paper, we compute the packing chromatic number for circular fans with two and four chords and mesh of trees.