|
Algebra and Discrete Mathematics, 2005, Issue 1, Pages 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
Abstract:
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.
Keywords:
hypergraph, color-detector, covering number.
Received: 18.10.2004 Revised: 24.03.2005
Citation:
I. V. Protasov, O. I. Protasova, “Color-detectors of hypergraphs”, Algebra Discrete Math., 2005, no. 1, 84–91
Linking options:
https://www.mathnet.ru/eng/adm291 https://www.mathnet.ru/eng/adm/y2005/i1/p84
|
|