List version of L(d,s)-labelings

AbstractLet G=(V,E) be a simple graph, and for all v∈V, let L(v) be a list of colors assigned to v. We shall assume throughout that the colors are natural numbers. For nonnegative integers d,s, define χℓd,s(G) to be the smallest integer k such that for every list assignment with |L(v)|=k for all v∈V one can choose a color c(v)∈L(v) for every vertex in such a way that |c(v)-c(w)|⩾d for all vw∈E and |c(v)-c(w)|⩾s for all pairs v,w of vertices having distance 2 in G. For a given list assignment such a coloring c is called an L(d,s)-list labeling.We prove a general bound for χℓd,s(G) depending on the maximum degree of G. Furthermore, we study this parameter for trees, and also for the particular classes of paths and stars. Polynomial algorithms are designed for deciding whether a given list assignment admits an L(d,s)-list labeling on paths (for a given s unrestricted) and on trees (for s=1)