Locally restricted colorings (Q2581565)

Let \(G\) be a graph with chromatic number \(\chi \geq 2.\) It is not difficult to see that for each \(\chi \)-coloring of \(G\) there is a vertex \(v\;\)so that each color occurs on some neighbour of \(v.\) It is shown in the paper that this property does not extend to \(k\)-colorings of \(G\) with \(k>\chi .\) Let \( \rho (\chi ,p)\) be the smallest number \(\rho \) so that for any graph \(G\) with chromatic number \(\chi \) and any coloring of \(G\) with \(\chi +p\) colors there is a vertex \(v\) so that at least \(\chi \) different collors occur at distance at most \(\rho \) from \(v.\) The authors prove that for all \(\chi \) and \(p\) it is \(\rho (\chi ,p)\leq \lceil \frac{p}{2}\rceil +1.\)