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

preprint2015arXivOpen access

Abstract

An ii-packing in a graph GG is a set of vertices at pairwise distance greater than ii. For a nondecreasing sequence of integers S=(s_1,s_2,…)S=(s\_{1},s\_{2},\ldots), the SS-packing chromatic number of a graph GG is the least integer kk such that there exists a coloring of GG into kk colors where each set of vertices colored ii, i=1,…,ki=1,\ldots, k, is an s_is\_i-packing. This paper describes various subdivisions of an ii-packing into jj-packings ($j\textgreater{}i$) for the hexagonal, square and triangular lattices. These results allow us to bound the SS-packing chromatic number for these graphs, with more precise bounds and exact values for sequences S=(s_i,i∈N∗)S=(s\_{i}, i\in\mathbb{N}^{*}), s_i=d+⌊(i−1)/n⌋s\_{i}=d+ \lfloor (i-1)/n \rfloor.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.