On n-stars in colorings and orientations of graphs

Abstract

An \(n\)-star \(S\) in a graph \(G\) is the union of geodesic intervals \(I _{1} , \ldots , I _{k} \) with common end \(O\) such that the subgraphs \(I_{ 1}\setminus\{O\}, \ldots , I _{k}\setminus\{O\}\) are pairwise disjoint and \(l(I _{1}) +\ldots + l(I _{k})= n.\) If the edges of \(G\) are oriented, \(S\) is directed if each ray \(I _{i}\) is directed. For natural number \(n, r\), we construct a graph \(G\) of \(\operatorname{diam} (G)=n\) such that, for any \(r\)-coloring and orientation of \(E(G)\), there exists a directed \(n\)-star with monochrome rays of pairwise distinct colors.