A seminal result of Dinur-Regev-Smyth from 2009 shows that for every $$q>0$$, finding a $$q$$-coloring of a 2-colorable 3-uniform hypergraph is quasi NP-hard. The techniques in this proof have been very influential in this subject. I will describe some recent extensions which prove inapproximability of various hypergraph coloring problems.
1. A rainbow $$q$$-coloring of a $$k$$-uniform hypergraph is a $$q$$-coloring of the vertex set such that every hyperedge contains all $$q$$ colors. Given a rainbow $$(k−2\sqrt{k})$$-colorable $$k$$-uniform hypergraph, it is NP-hard to find a normal 2-coloring.
2. A $$(q,p)$$-coloring is a coloring using $$q$$ colors such that every hyperedge contains at least $$p$$ colors. We prove that given a rainbow $$(k-\sqrt{ck}, k-3\sqrt{ck})$$-colorable $$k$$-uniform hypergraph, it is NP-hard to find a normal $$c$$-coloring for any $$c=o(k)$$. This relies on two combinatorial theorems: one of the theorems was proved by Sarkaria using topological methods and the other theorem we prove using a generalized Borsuk-Ulam theorem.