Minimum span of no-hole \((r+1)\)-distant colorings (Q2753531)

The paper considers the problem of assigning non-negative integral channels to a set of transmitters under the constraint that, if two transmitters interfere, the difference between their channels is greater then \(r,\) for a given non-negative integer \(r\). The problem is modelled by means of a graph \(G\) whose vertices represent the transmitters and two vertices are joined if and only if their corresponding transmitters interfere. A no-hole \((r+1)\){-distant coloring}, called an \(N_{r}\)-coloring, is a function \(f\) that assigns a non-negative integer to each vertex of \(G\) such that \(\left\{ f(v):v\in V(G)\right\} \) is a consecutive set and \(\left|f(u)-f(v)\right|>r\) if \(uv\in E(G).\) The span of an \(N_{r}\)-coloring is the difference between the largest and smallest colors used in the coloring. The \(N_{r}\)-span of \(G\) is the minimum span among all \(N_{r}\)-colorings of \(G\) if \(G\) has an \(N_{r}\)-coloring; otherwise nsp\(_{r}(G)=\infty .\) The values of the \(N_{1}\)-span for all bipartite graphs can be deduced from a result of \textit{F. S. Roberts} [Math. Comput. Modelling 17, No. 11, 139-144 (1993; Zbl 0786.05036)]. In this paper the values of the \(N_{2}\)-span are found for all bipartite graphs.