Decomposing hypergraphs into $k$-colorable hypergraphs

Document Type: Research Paper

Authors

1 Isfahan University of Technology

2 Tarbiat Modares University

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 $1\leq i\leq l$ is $k$-colorable‎, ‎is $\lceil‎ ‎\log_{k} \chi(H) \rceil$‎.

Keywords

Main Subjects


B. D. Acharya (1983). Even edge colorings of a graph. J. Combin. Theory Ser. B. 35, 78-79
N. Alon and Y. Egawa (1985). Even edge colorings of a graph. J. Combin. Theory Ser. B. 38, 93-94