Dichotomies properties on computational complexity of S-packing coloring problems - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics Année : 2015

Dichotomies properties on computational complexity of S-packing coloring problems

(1)
1
Nicolas Gastineau
  • Fonction : Auteur correspondant
  • PersonId : 950056

Connectez-vous pour contacter l'auteur

Résumé

This work establishes the complexity class of several instances of the S-packing coloring problem: for a graph G, a positive integer k and a non decreasing list of integers S = (s_1 , ..., s_k ), G is S-colorable, if its vertices can be partitioned into sets S_i , i = 1,... , k, where each S_i being a s_i -packing (a set of vertices at pairwise distance greater than s_i). For a list of three integers, a dichotomy between NP-complete problems and polynomial time solvable problems is determined for subcubic graphs. Moreover, for an unfixed size of list, the complexity of the S-packing coloring problem is determined for several instances of the problem. These properties are used in order to prove a dichotomy between NP-complete problems and polynomial time solvable problems for lists of at most four integers.
Fichier principal
Vignette du fichier
comp_S_packing_arxiv.pdf (253.82 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00920502 , version 1 (18-12-2013)
hal-00920502 , version 2 (17-07-2014)
hal-00920502 , version 3 (29-01-2015)

Licence

Paternité - CC BY 4.0

Identifiants

Citer

Nicolas Gastineau. Dichotomies properties on computational complexity of S-packing coloring problems. Discrete Mathematics, 2015, 338, pp.1029-1041. ⟨hal-00920502v3⟩
226 Consultations
171 Téléchargements

Altmetric

Partager

Gmail Facebook Twitter LinkedIn More