The \(L(2,1)\)-labeling on planar graphs (Q868019): Difference between revisions

For a simple graph \(G\), \(\lambda (G)\) is the smallest non-negative integer \(m\) such that there is a function \(f\) from \(V(G)\) to the set of non-negative integers which has the property that \(| f(u)-f(v)| \geq 2\) if \(d(u,v)=1\) and \(| f(u)-f(v)| \geq 1\) if \(d(u,v)=2\). Using standard inequalities derived from Euler's theorem and a few other well-known results, the authors derive a series of upper bounds on \(\lambda\) which improve on known results for planar graphs of appropriately low maximum degree. In 1992, Griggs and Yeh conjectured that for \(G\) with maximum degree \(\Delta\), \(\lambda \leq \Delta^{2}\); see \textit{J. R. Griggs} and \textit{R. K. Yeh} [SIAM J. Discrete Math. 5, 586--595 (1992; Zbl 0767.05080)]. In the present paper an infinite sequence of graphs satisfying the conjecture is presented.