Accéder directement au contenu Accéder directement à la navigation
Pré-publication, Document de travail

S-Packing Colorings of Cubic Graphs

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 :
Pré-publication, Document de travail
Liste complète des métadonnées

https://hal-univ-bourgogne.archives-ouvertes.fr/hal-00967446
Contributeur : Olivier Togni Connectez-vous pour contacter le contributeur
Soumis le : vendredi 28 mars 2014 - 15:42:56
Dernière modification le : mardi 19 octobre 2021 - 11:45:39
Archivage à long terme le : : samedi 28 juin 2014 - 12:05:10

Fichiers

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

Identifiants

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

Citation

Nicolas Gastineau, Olivier Togni. S-Packing Colorings of Cubic Graphs. 2014. ⟨hal-00967446v1⟩

Partager

Métriques

Consultations de la notice

433

Téléchargements de fichiers

273