On the Complexity of the S-coloring problem
Nicolas Gastineau · arXiv (Cornell University) · 2013
AbstractThis work establishes the complexity class of several instances of the S-coloring problem: For a graph G, a positive integer kand a non decreasinglist of integers S=(s 1 ,...,s k ), Gadmits a S-coloring, if its vertices can bepartitioned into sets X s i , i=1,...,k, where each X s i being an s i -packing(a set of vertices at pairwise distance greater than s i ). For a unfixed sizeof list, the complexity of the S-coloring problem is determined for severalinstances of the problem. Keywords: NP-hard problem, distance, Packing chromatic number,d-distance coloring. 1 Introduction We consider only undirected connected graphs in this paper. Given a graphG=(V,E), an i -packing is a set X i ⊆ V(G)such that for any distinct pair u,v ∈ X i , d G (u,v)>i, where d G (u,v) denotes the usual shortest path distancebetween uand v. We will use X i to refer to an i-packing in a graph G. For a nondecreasing sequence of positive integers S=(s i ,i∈ N ∗ ), an S - k -coloring of Gisa partition of V(G)into sets X