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

Abstract : 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$.
Type de document :
Article dans une revue
Ars Mathematica Contemporanea, DMFA Slovenije, 2015, 9
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal-univ-bourgogne.archives-ouvertes.fr/hal-01157901
Contributeur : Nicolas Gastineau <>
Soumis le : jeudi 28 mai 2015 - 18:35:44
Dernière modification le : vendredi 10 novembre 2017 - 01:22:01
Document(s) archivé(s) le : mardi 15 septembre 2015 - 08:01:52

Fichiers

sub_packacv-hal.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • HAL Id : hal-01157901, version 1
  • ARXIV : 1505.07781

Collections

Citation

Nicolas Gastineau, Hamamache Kheddouci, Olivier Togni. Subdivision into i-packings and S-packing chromatic number of some lattices. Ars Mathematica Contemporanea, DMFA Slovenije, 2015, 9. 〈hal-01157901〉

Partager

Métriques

Consultations de la notice

568

Téléchargements de fichiers

112