2015/05/28 by Nicolas Gastineau, Gastineau, Nicolas, Hamamache Kheddouci +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1505.07781
arxiv created 2015/05/28 · arxiv updated 2015/05/29
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\textgreateri) 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∈ℕ*), s_i=d+ \lfloor (i-1)/n \rfloor.