S-Packing Colorings of Cubic Graphs

Nicolas Gastineau 1 Olivier Togni 2
1 GrAMA - Graphes, Algorithmes et Multi-Agents
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
Abstract : Given a non-decreasing sequence $S=(s_1,s_2, \ldots, s_k)$ of positive integers, an {\em $S$-packing coloring} of a graph $G$ is a mapping $c$ from $V(G)$ to $\{s_1,s_2, \ldots, s_k\}$ such that any two vertices with color $s_i$ are at mutual distance greater than $s_i$, $1\le i\le k$. This paper studies $S$-packing colorings of (sub)cubic graphs. We prove that subcubic graphs are $(1,2,2,2,2,2,2)$-packing colorable and $(1,1,2,2,3)$-packing colorable. For subdivisions of subcubic graphs we derive sharper bounds, and we provide an example of a cubic graph of order $38$ which is not $(1,2,\ldots,12)$-packing colorable.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2016, 339, pp.2461-2470
Liste complète des métadonnées


https://hal-univ-bourgogne.archives-ouvertes.fr/hal-00967446
Contributeur : Nicolas Gastineau <>
Soumis le : vendredi 29 avril 2016 - 12:15:53
Dernière modification le : mercredi 18 mai 2016 - 19:26:56
Document(s) archivé(s) le : lundi 23 mai 2016 - 16:43:54

Fichiers

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

Identifiants

  • HAL Id : hal-00967446, version 2
  • ARXIV : 1403.7495

Collections

Citation

Nicolas Gastineau, Olivier Togni. S-Packing Colorings of Cubic Graphs. Discrete Mathematics, Elsevier, 2016, 339, pp.2461-2470. <hal-00967446v2>

Partager

Métriques

Consultations de
la notice

134

Téléchargements du document

99