What is the best lower bound in terms of $k$ on the number of edges in a $3$-uniform hypergraph that is not $k$-colorable?
Is it true that any $3$-uniform hypergraph that is not $k$-colorable must have $\Omega(k^3)$ edges?
TCS-user-23
- 53
- 4