Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number (Q1092065)

The main results of this article are the representation of algorithms for several strong coloring problems (that are well-defined partitions of the set of vertices of a hypergraph in certain color sets) and the analysis of their performance in spaces of random hypergraphs. The so-called strong coloring algorithms \({\mathfrak KL}\gamma\) are fully described, they are proved in detail by using many theorems and lemmata and they exist of three phases which are analysed exactly. Furthermore it is shown that in these spaces the number of colors which are used by these algorithms is almost surely within a small constant factor (less than 4) of the strong chromatic number of the hypergraph. The article also contains a small summary of theorems concerning weak colorings and sparse hypergraphs and refers to some questions which are left open.