|
|
Algebra and Discrete Mathematics, 2016, Volume 22, Issue 2, Pages 301–303
(Mi adm589)
|
|
|
|
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.
Received: 30.09.2016 Revised: 03.10.2016
Citation:
Igor Protasov, “On $n$-stars in colorings and orientations of graphs”, Algebra Discrete Math., 22:2 (2016), 301–303
Linking options:
https://www.mathnet.ru/eng/adm589 https://www.mathnet.ru/eng/adm/v22/i2/p301
|
|