Fixed-parameter complexity of \(\lambda\)-labelings (Q5948961)

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\geq 1\) that there are several \(\lambda\) such that deciding if \(L(G;p,q) \leq \lambda\) is NP-complete (taking \(\lambda\) here as fixed part of the problem description). Some other related results are also shown.