On n-stars in colorings and orientations of graphs

Igor Vladimirovich Protasov


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.


n-star, coloring, orientation.

Full Text:



M. Cochand, P. Duchet, A few remarks on orientations of graphs and Ram-

sey theory, in: Irregularities of Partitions, Algorithms and Combinatorics 8

(eds. Halasz, G., and Sos, V.T.) Springer-Verlag, Berlin (1989), 39-46.

J. Nesetril, V. Rodl, Sparse Ramsey graphs, Combinatorica 4: 1 (1984) 71-

I. Kohayakawa, T. Luczak, V. Rodl, Ramsey-type results for oriented trees,

J. Graph Theory 22: 1 (1996) 1-8.


  • There are currently no refbacks.