Coloring of Hypergraphs

Hypergraphs are discrete structures that generalize graphs in a very natural way. While in a graph every edge is incident with exactly two vertices, in a hypergraph an edge may be incident with more than two vertices. So hypergraphs model more general types of relations than graphs, and hypergraphs have proved also to be of major interest in applications to real-world problems. Most concepts and problems for graphs can be extended to hypergraphs in natural ways, and sometimes this is indispensable and leads to a better understanding of the original concept and problem. Clearly, since graphs are special cases of hypergraphs, problems for hypergraphs are at least as hard as its specialized versions to the graph case. Coloring of hypergraphs were first defined and investigated by Erd˝os and Hajnal in the 1960s.