Approximating coloring and maximum independent sets in 3-uniform hypergraphs

We discuss approximation algorithms for the coloring problem and the maximu m independent set problem in 3-uniform hypergraphs. An algorithm for colori ng 3-uniform 2-colorable hypergraphs in (O) over tilde (n(1/5)) colors is p resented, improving previously known results. Also, for every fixed gamma > 1/2, we describe an algorithm that, given a 3-uniform hypergraph H on n ve rtices with an independent set of size gamman, finds an independent set of size <(<Omega>)over bar>(min(n, n(6 gamma -3))). For certain values of gamm a we are able to improve this using the local ratio approach. The results a re obtained through semidefinite programming relaxations of these optimizat ion problems. (C) 2001 Academic Press.