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

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

MSC: 05C15

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

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



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


© МИАН, 2024