A

$\lambda (p,q)$ labelling of a graph

$G=(V,E)$ is an assignment of non-negative integers to the vertices in

$V$, such that adjacent vertices get labels that differ by at least

$p$, and vertices of distance two in

$G$ get labels that differ by at least

$q$.

$L(G;p,q)$ is the minimum possible maximum value in a

$\lambda (p,q)$ labelling of

$G$. The standard

$\lambda $-coloring problem is to determine

$L(G;2,1)$ of a graph. This paper shows that this problem is solvable in polynomial time on almost

$k$-trees (graphs that can be formed by adding

$k$ edges to a tree), and is NP-hard for every fixed maximum label value. It is also shown for all values

$p>q\ge 1$ that there are several

$\lambda $ such that deciding if

$L(G;p,q)\le \lambda $ is NP-complete (taking

$\lambda $ here as fixed part of the problem description). Some other related results are also shown.