Dichotomies properties on computational complexity of S-packing coloring problems

Nicolas Gastineau 1, *
* Auteur correspondant
1 Equipe Combinatoire
Le2i - Laboratoire Electronique, Informatique et Image
Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2015, 338, pp.1029-1041
Liste complète des métadonnées


https://hal-univ-bourgogne.archives-ouvertes.fr/hal-00920502
Contributeur : Nicolas Gastineau <>
Soumis le : jeudi 29 janvier 2015 - 19:19:31
Dernière modification le : vendredi 29 avril 2016 - 18:22:43
Document(s) archivé(s) le : jeudi 30 avril 2015 - 12:00:13

Fichiers

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

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • HAL Id : hal-00920502, version 3
  • ARXIV : 1312.5280

Collections

Citation

Nicolas Gastineau. Dichotomies properties on computational complexity of S-packing coloring problems. Discrete Mathematics, Elsevier, 2015, 338, pp.1029-1041. <hal-00920502v3>

Partager

Métriques

Consultations de
la notice

91

Téléchargements du document

55