On S-packing edge-colorings of cubic graphs

Abstract : Given a non-decreasing sequence S = (s 1,s 2,. .. ,s k) of positive integers, an S-packing edge-coloring of a graph G is a partition of the edge set of G into k subsets {X 1 ,X 2,. .. ,X k } such that for each 1 ≤ i ≤ k, the distance between two distinct edges e, e ′ ∈ X i is at least s i + 1. This paper studies S-packing edge-colorings of cubic graphs. Among other results, we prove that cubic graphs having a 2-factor are (1,1,1,3,3)-packing edge-colorable, (1,1,1,4,4,4,4,4)-packing edge-colorable and (1,1,2,2,2,2,2)-packing edge-colorable. We determine sharper results for cubic graphs of bounded oddness and 3-edge-colorable cubic graphs and we propose many open problems.
Type de document :
Pré-publication, Document de travail
2017
Liste complète des métadonnées

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

https://hal-univ-bourgogne.archives-ouvertes.fr/hal-01651260
Contributeur : Nicolas Gastineau <>
Soumis le : mardi 28 novembre 2017 - 18:32:20
Dernière modification le : vendredi 8 décembre 2017 - 10:50:25

Fichiers

packing-edgeVhal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01651260, version 1
  • ARXIV : 1711.10906

Collections

Citation

Nicolas Gastineau, Olivier Togni. On S-packing edge-colorings of cubic graphs. 2017. 〈hal-01651260〉

Partager

Métriques

Consultations de la notice

7

Téléchargements de fichiers

3