| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652661 | Electronic Notes in Discrete Mathematics | 2008 | 5 Pages |
Abstract
A subset A of vertices in a graph G is an r-packing if the distance between every pair of distinct vertices in A is more than r. The packing chromatic number, χρ(G), is the smallest k for which there exists some partition V1,V2,…,Vk of the vertex set of G such that Vr is an r-packing. We obtain lower and upper bounds for the packing chromatic number of Cartesian products and subdivisions of finite graphs and study the existence of monotone colorings in trees. The infinite, planar triangular lattice and the three dimensional square lattice are shown to have unbounded packing chromatic number.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
