6533b854fe1ef96bd12ae8b2
RESEARCH PRODUCT
Dichotomies properties on computational complexity of S-packing coloring problems
Nicolas Gastineausubject
Discrete mathematicsDichotomyComputational complexity theory010102 general mathematics0102 computer and information sciences01 natural sciencesGraphTheoretical Computer ScienceCombinatoricsIntegerSet packing010201 computation theory & mathematicsComplexity classDiscrete Mathematics and CombinatoricsPairwise comparison0101 mathematicsColoring problemMathematicsdescription
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 , i = 1 , ? , k , where each S i is an s i -packing (a set of vertices at pairwise distance greater than s i ). In particular we prove a dichotomy between NP-complete problems and polynomial-time solvable problems for lists of at most four integers.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2015-06-01 | Discrete Mathematics |