Subdivision into i-packings and S-packing chromatic number of some lattices - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Ars Mathematica Contemporanea Année : 2015

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

(1) , (2) , (1)
1
2

Résumé

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$.
Fichier principal
Vignette du fichier
sub_packacv-hal.pdf (258.39 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01157901 , version 1 (28-05-2015)

Licence

Paternité - CC BY 4.0

Identifiants

Citer

Nicolas Gastineau, Hamamache Kheddouci, Olivier Togni. Subdivision into i-packings and S-packing chromatic number of some lattices. Ars Mathematica Contemporanea, 2015, 9. ⟨hal-01157901⟩
482 Consultations
155 Téléchargements

Altmetric

Partager

Gmail Facebook Twitter LinkedIn More