ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

Packing chromatic number of cycle related graphs

Journal: International Journal of Mathematics and Soft Computing (Vol.4, No. 1)

Publication Date:

Authors : ; ; ;

Page : 27-33

Keywords : Packing chromatic number; kCn - linear; barbell graph; split graph; total graph; crown graph; lollipop; tadpole.;

Source : Downloadexternal Find it from : Google Scholarexternal

Abstract

The packing chromatic number $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 give the packing chromatic number for some classes of cycles.

Last modified: 2017-08-30 18:57:40