Dichotomies properties on computational complexity of S-packing coloring problems
| Affiliation auteurs | !!!! Error affiliation !!!! |
| Titre | Dichotomies properties on computational complexity of S-packing coloring problems |
| Type de publication | Journal Article |
| Year of Publication | 2015 |
| Auteurs | Gastineau N |
| Journal | DISCRETE MATHEMATICS |
| Volume | 338 |
| Pagination | 1029-1041 |
| Date Published | JUN 6 |
| Type of Article | Article |
| ISSN | 0012-365X |
| Mots-clés | d-distance coloring, Graph, NP-complete problem, Packing chromatic number, S-packing chromatic number |
| 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 nondecreasing list of integers S = (S-1, ..., s(k)), G is S-colorable if its vertices can be partitioned into sets S-i |
| DOI | 10.1016/j.disc.2015.01.028 |