IJPAM: Volume 87, No. 6 (2013)

PACKING CHROMATIC NUMBER OF CERTAIN GRAPHS

Albert William$^1$, S. Roy$^2$
$^{1,2}$Department of Mathematics
Loyola College
Chennai 600 034, INDIA


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 broadcasting coloring. It is proved that packing coloring is NP-complete for general graphs and even for trees. In this paper, we study the packing chromatic number of comb graph, circular ladder, windmill, H-graph and uniform theta graph.

Received: September 6, 2013

AMS Subject Classification: 05C15

Key Words and Phrases: packing chromatic number, comb graph, circular ladder, windmill, $H$-graph, uniform theta graph

Download paper from here.


DOI: 10.12732/ijpam.v87i6.1 How to cite this paper?
Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2013
Volume: 87
Issue: 6