The Complexity of Vertex Coloring Problems in Dense Uniform Hypergraphs

Combinatorics Seminar
Friday, April 30, 2010 - 3:05pm
1 hour (actually 50 minutes)
Skiles 255
Adam Mickiewicz University
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.