RUS  ENG
Полная версия
ЖУРНАЛЫ // Algebra and Discrete Mathematics // Архив

Algebra Discrete Math., 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.

MSC: 05C55

Поступила в редакцию: 30.09.2016
Исправленный вариант: 03.10.2016

Язык публикации: английский



Реферативные базы данных:


© МИАН, 2024