On the hardness of computing span of subcubic graphs

•Computing the span of subcubic graphs is NP-hard in the strong sense.•It is polynomially solvable and approximable under some extra assumptions.

Given a nonempty graph G and a function ξ that assigns positive integers to the edges of G, a ξ-coloring of G is a vertex coloring of G such that for every edge uv of G the colors assigned to the vertices u and v   differ by at least ξ(uv)ξ(uv). In the paper we study the problem of finding ξ-colorings with minimal span, i.e. the difference between the largest and the smallest color used. We show that the problem, restricted to subcubic graphs, is:•NP-hard in the strong sense but polynomially 32-approximable for functions ξ that take at most two values;•polynomially 2-approximable and not (1+ε)(1+ε)-approximable for any ε<12, unless P=NPP=NP. We also show that, if we additionally assume that the edges that received the largest of the values of ξ induce a spanning and connected subgraph, then it becomes•polynomially 43-approximable;•polynomially solvable provided ξ takes at most two values.