6533b82dfe1ef96bd1291fa9

RESEARCH PRODUCT

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

subject

description

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,\ldots)$?, 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,\ldots,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$?. Množici vozlišč grafa ?$G$?, paroma oddaljenih za več kot ?$i$?, pravimo ?$i$?-pakiranje. Če je ?$S=(s_1,s_2,\ldots)$? nepadajoče zaporedje celih števil, potem je ?$S$?-pakirno kromatsko število grafa ?$G$? najmanjše celo število ?$k$?, pri katerem obstaja barvanje grafa ?$G$? s ?$k$? barvami, v katerem vsaka množica vozlišč, pobarvanih z barvo ?$i$?, ?$i=1,\ldots,k$?, predstavlja ?$s_i$?-pakiranje. Članek opisuje različne podrazdelitve ?$i$?-pakiranj na ?$j$?-pakiranja ?$(j>i)$? za šestkotniške, kvadratne in trikotniške mreže. Ti rezultati nam omogočajo omejiti ?$S$?-pakirno kromatsko število teh grafov in določiti natančnejše meje in natančne vrednosti za zaporedja ?$S=(s_i,i \in \mathbb{N}^*)$?, ?$s_i = d+ \lfloor (i-1)/n \rfloor$?.