• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

On S-packing edge-colorings of cubic graphs

Gastineau, Nicolas; Togni, Olivier (2019), On S-packing edge-colorings of cubic graphs, Discrete Applied Mathematics, 259, p. 63-75. 10.1016/j.dam.2018.12.035

Type
Article accepté pour publication ou publié
External document link
https://hal-univ-bourgogne.archives-ouvertes.fr/hal-01651260
Date
2019
Journal name
Discrete Applied Mathematics
Volume
259
Publisher
Elsevier
Pages
63-75
Publication identifier
10.1016/j.dam.2018.12.035
Metadata
Show full item record
Author(s)
Gastineau, Nicolas
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Togni, Olivier cc
Abstract (EN)
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.
Subjects / Keywords
Cubic graph; Packing chromatic index; S-packing chromatic index; Snark; d,-distance coloring

Related items

Showing items related by title and author.

  • Thumbnail
    On the packing chromatic number of subcubic outerplanar graphs 
    Gastineau, Nicolas; Holub, Přemysl; Togni, Olivier (2019) Article accepté pour publication ou publié
  • Thumbnail
    Approximating the max edge-coloring problem 
    Bourgeois, Nicolas; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2010) Article accepté pour publication ou publié
  • Thumbnail
    Approximating the max edge-coloring problem 
    Bourgeois, Nicolas; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2009) Communication / Conférence
  • Thumbnail
    Complexity of two coloring problems in cubic planar bipartite mixed graphs 
    Ries, Bernard (2010) Article accepté pour publication ou publié
  • Thumbnail
    Optimal edge-coloring with edge rate constraints 
    Dereniowski, Dariusz; Kubiak, W.; Ries, Bernard; Zwols, Yori (2013) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo