Subdivision into i-packings and S-packing chromatic number of some lattices - Gastineau, Nicolas (Ars mathematica contemporanea, 2015)
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 \mathbb{N}^*)$?, ?$s_i = d+ \lfloor (i-1)/n \rfloor$?.
Keywords: distance coloring; hexagonal lattice; i-packing; i-pakiranje; kvadratna mreža; packing chromatic number; pakirno kromatsko število; razdaljno barvanje; square lattice; šestkotniška mreža; triangular lattice; trikotniška mreža