|
Algebra and Discrete Mathematics, 2005, выпуск 1, страницы 84–91
(Mi adm291)
|
|
|
|
RESEARCH ARTICLE
Color-detectors of hypergraphs
I. V. Protasov, O. I. Protasova Department of Cybernetics, Kyiv University, Volodimirska 64, Kyiv GSP, Ukraine
Аннотация:
Let $X$ be a set of cardinality $k$, $\mathcal{F}$ be a family of subsets of $X$. We say that a cardinal $\lambda,\lambda<k$, is a color-detector of the hypergraph $H=(X,\mathcal{F})$ if card $\chi(X)\leq \lambda$ for every coloring $\chi: X\rightarrow k$ such that card $\chi(F)\leq \lambda$ for every $F\in\mathcal{F}$. We show that the color-detectors of $H$ are tightly connected with the covering number $ cov(H)=\mathrm{cup}\{\alpha:\text{any }\alpha\text{points of }X\text{ are contained in some }F\in\mathcal F\}$. In some cases we determine all of the color-detectors of $H$ and their asymptotic counterparts. We put also some open questions.
Ключевые слова:
hypergraph, color-detector, covering number.
Поступила в редакцию: 18.10.2004 Исправленный вариант: 24.03.2005
Образец цитирования:
I. V. Protasov, O. I. Protasova, “Color-detectors of hypergraphs”, Algebra Discrete Math., 2005, no. 1, 84–91
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/adm291 https://www.mathnet.ru/rus/adm/y2005/i1/p84
|
Статистика просмотров: |
Страница аннотации: | 108 | PDF полного текста: | 61 | Первая страница: | 1 |
|