Transactions on Combinatorics (Jun 2014)

Decomposing hypergraphs into k-colorable hypergraphs

  • Gholamreza Omidi ,
  • Khosro Tajbakhsh

Journal volume & issue
Vol. 3, no. 2
pp. 31 – 33

Abstract

Read online

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