Optimal frequency assignment and planar list \(L(2, 1)\)-labeling (Q2084641)

The \(L(2, 1)\) labeling problem is well known in frequency assignment tasks aiming to avoid interference. \textit{J. R. Griggs} and \textit{R. K. Yeh} [SIAM J. Discrete Math. 5, No. 4, 586--595 (1992; Zbl 0767.05080)] conjectured that for a graph \(G\), with maximum degree \(k\), the minimum span of the \(L(2, 1)\) labeling is at most \(k^2\). The authors successfully establish that for a planar graph with maximum degree \(k\) of at least 5, and girth of at least 13, the minimum span of the \(L(2, 1)\) labeling is at most \(k+3\) and it is a tight upper bound.