RESEARCH ARTICLE

On $n$-stars in colorings and orientations of graphs

Igor Protasov

Department of Cybernetics, Kyiv University, Volodymyrska 64, 01033, Kyiv, Ukraine

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.

Keywords: $n$-star, coloring, orientation.

MSC: 05C55

Received: 30.09.2016
Revised: 03.10.2016

Language: English

Bibliographic databases:

• 
•