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.

MSC: 05C15

Received: 18.10.2004
Revised: 24.03.2005

Language: English

Bibliographic databases:

• 
•