Georgia Institute of Technology College of Sciences

In the talk we will consider the problem of deciding whether agiven $r$-uniform hypergraph $H$ with minimum vertex degree atleast $c|V(H)|$, has a vertex 2-coloring. This problem has beenknown also as the Property B of a hypergraph. Motivated by an oldresult of Edwards for graphs, we summarize what can be deducedfrom his method about the complexity of the problem for densehypergraphs. We obtain the optimal dichotomy results for2-colorings of $r$-uniform hypergraphs when $r=3,4,$ and 5. During the talk we will present the NP-completeness results followed bypolynomial time algorithms for the problems above the thresholdvalue. The coloring algorithms rely on the known Tur\'{a}n numbersfor graphs and hypergraphs and the hypergraph removal lemma.