Decomposing hypergraphs into k-colorable hypergraphs

Abstract

For a given hypergraph $H$ with chromatic number $chi(H)$ and with no edge containing only one vertex, it is shown that the minimum number $l$ for which there exists a partition (also a covering) ${E_1,E_2,ldots,E_l}$ for $E(H)$, such that the hypergraph induced by $E_i$ for each $1leq ileq l$ is $k$-colorable, is $lceil log_{k} chi(H) rceil$.

Keywords

• Hypergraph
• chromatic number
• k-Colorable