On two-coloring bipartite uniform hypergraphs

Boyoon Lee, Theodore Molla, Brendan Nagle

Of a given bipartite graph $G=(V,E)$, it is elementary to construct a bipartition in time $O(|V|+|E|)$. For a given $k$-graph $H=H^{(k)}$ with $k\ge 3$ fixed, Lovász prov…