Subdivision into i-packings and S-packing chromatic number of some lattices

Nicolas Gastineau, Hamamache Kheddouci, Olivier Togni


An i-packing in a graph G is a set of vertices at pairwise distance greater than i. For a nondecreasing sequence of integers S=(s_1,s_2,...), the S-packing chromatic number of a graph G is the least integer k such that there exists a coloring of G into k colors where each set of vertices colored i, i=1,..., k, is an s_i-packing.

This paper describes various subdivisions of an i-packing into j-packings (j>i) for the hexagonal, square and triangular lattices. These results allow us to bound the S-packing chromatic number for these graphs, with more precise bounds and exact values for sequences S=(s_i, i in N*), s_i = d+ [(i-1)/n].


Packing chromatic number, i-packing, hexagonal lattice, square lattice, triangular lattice, distance coloring.

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications