On the packing chromatic number of Cartesian products, hexagonal lattice, and trees

The packing chromatic number χρ(G) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into k packings with pairwise different widths. Several lower and upper bounds are obtained for the packing chromatic number of Cartesian products of graphs. It is proved that the packing chromatic number of the infinite hexagonal lattice lies between 6 and 8. Optimal lower and upper bounds are proved for subdivision graphs. Trees are also considered and monotone colorings are introduced.