|
Algebra and Discrete Mathematics, 2016, том 22, выпуск 2, страницы 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
Аннотация:
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.
Поступила в редакцию: 30.09.2016 Исправленный вариант: 03.10.2016
Образец цитирования:
Igor Protasov, “On $n$-stars in colorings and orientations of graphs”, Algebra Discrete Math., 22:2 (2016), 301–303
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/adm589 https://www.mathnet.ru/rus/adm/v22/i2/p301
|
Статистика просмотров: |
Страница аннотации: | 177 | PDF полного текста: | 73 | Список литературы: | 44 |
|