Labeling chordal graphs: Distance two condition. (English) Zbl 0794.05118
An \(L_ d(2,1)\)-labeling \(f\) of a graph \(G= (V,E)\) is a map \(f: V\to \mathbb{R}^ +\cup \{0\}\) with the property that, if \(x\) and \(y\) are two adjacent vertices, then \(| f(x)- f(y)|\geq 2d\), and, if the distance between \(x\) and \(y\) is two, then \(| f(x)- f(y)|\geq d\), \(d\in \mathbb{R}^ +\). Putting \(d=1\) the author investigates the so-called \(L(2,1)\)-labeling number \(\lambda(G)\) of \(G\) and determines upper bounds of \(\lambda(G)\), \(G\) is an arbitrary chordal graph, depending on the maximum degree \(\Delta(G)\). In the second part, the author considers unit interval graphs \(G\) and then succeeds in finding a better upper bound of \(\lambda(G)\) depending on the chromatic number \(\chi(G)\). The author concludes his paper by formulating some open problems on upper bounds of the \(L(2,1)\)-labeling number \(\lambda(G)\).
Reviewer: R.Bodendiek (Kiel)