Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number

AbstractWe present coloring algorithms for several strong coloring problems and analyze their performance in spaces of random hypergraphs. In these spaces the number of colors used by our algorithms is almost surely within a small constant factor (less than 4) of the strong chromatic number of the hypergraph