On Packing Colorings of Distance Graphs

Abstract : The {\em packing chromatic number} $\chi_{\rho}(G)$ of a graph $G$ is the least integer $k$ for which there exists a mapping $f$ from $V(G)$ to $\{1,2,\ldots ,k\}$ such that any two vertices of color $i$ are at distance at least $i+1$. This paper studies the packing chromatic number of infinite distance graphs $G(\mathbb{Z},D)$, i.e. graphs with the set $\mathbb{Z}$ of integers as vertex set, with two distinct vertices $i,j\in \mathbb{Z}$ being adjacent if and only if $|i-j|\in D$. We present lower and upper bounds for $\chi_{\rho}(G(\mathbb{Z},D))$, showing that for finite $D$, the packing chromatic number is finite. Our main result concerns distance graphs with $D=\{1,t\}$ for which we prove some upper bounds on their packing chromatic numbers, the smaller ones being for $t\geq 447$: $\chi_{\rho}(G(\mathbb{Z},\{1,t\}))\leq 40$ if $t$ is odd and $\chi_{\rho}(G(\mathbb{Z},\{1,t\}))\leq 81$ if $t$ is even.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2014, 167, pp.280-289. <10.1016/j.dam.2013.10.026>
Liste complète des métadonnées


https://hal-univ-bourgogne.archives-ouvertes.fr/hal-00531583
Contributeur : Olivier Togni <>
Soumis le : jeudi 20 février 2014 - 14:56:57
Dernière modification le : jeudi 20 février 2014 - 15:59:15
Document(s) archivé(s) le : vendredi 7 avril 2017 - 23:31:38

Fichiers

PCDTogniRevisedV2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Olivier Togni. On Packing Colorings of Distance Graphs. Discrete Applied Mathematics, Elsevier, 2014, 167, pp.280-289. <10.1016/j.dam.2013.10.026>. <hal-00531583v2>

Partager

Métriques

Consultations de
la notice

162

Téléchargements du document

100