The following paper of Alon shows that the quantity you're after, $m(k)$, the minimum number of edges of a $3$-uniform hypergraph which is not $k$-colourable, is indeed $\asymp k^3$.

More precisely, he shows that

$$ 2\left\lceil \frac{k-1}{3}\right\rceil \left\lfloor \frac{2}{3}(k-1)\right\rfloor^2 < m(k) \leq \frac{\log 3}{2(\log 3-1)}\binom{3k-2}{3}$$

where the implied constants are absolute. The lower bound follows from a simple probabilistic argument -- colour all the vertices randomly, and then recolour a few necessary vertices to remove the small number of monochromatic edges which remain.

http://www.tau.ac.il/~nogaa/PDFS/Publications/Hypergraphs%20with%20high%20chromatic%20number.pdf

The following paper of Alon shows that the quantity you're after, $m(k)$, the minimum number of edges of a $3$-uniform hypergraph which is not $k$-colourable, is indeed $\asymp k^3$.

More precisely, he shows that

$$ 2\left\lceil \frac{k}{3}\right\rceil \left\lfloor \frac{2k}{3}\right\rfloor^2 < m(k) \leq \binom{2k+1}{3}$$

where the implied constants are absolute. The lower bound follows from a simple probabilistic argument -- colour all the vertices randomly, and then recolour a few necessary vertices to remove the small number of monochromatic edges which remain. The upper bound is just the number of edges of the complete 3-uniform hypergraph on $2k+1$ vertices, which is clearly not $k$-colourable

http://www.tau.ac.il/~nogaa/PDFS/Publications/Hypergraphs%20with%20high%20chromatic%20number.pdf

The following paper of Alon shows that the quantity you're after, $m(k)$, the minimum number of edges of a $3$-uniform hypergraph which is not $k$-colourable, is indeed $\asymp k^3$.

More precisely, he shows that

$$ k^3\ll m(k) \ll \binom{3k-2}{3}$$

where the implied constants are absolute. The lower bound follows from a simple probabilistic argument -- colour all the vertices randomly, and then recolour a few necessary vertices to remove the small number of monochromatic edges which remain.

http://www.tau.ac.il/~nogaa/PDFS/Publications/Hypergraphs%20with%20high%20chromatic%20number.pdf

The following paper of Alon shows that the quantity you're after, $m(k)$, the minimum number of edges of a $3$-uniform hypergraph which is not $k$-colourable, is indeed $\asymp k^3$.

More precisely, he shows that

$$ 2\left\lceil \frac{k-1}{3}\right\rceil \left\lfloor \frac{2}{3}(k-1)\right\rfloor^2 < m(k) \leq \frac{\log 3}{2(\log 3-1)}\binom{3k-2}{3}$$

where the implied constants are absolute. The lower bound follows from a simple probabilistic argument -- colour all the vertices randomly, and then recolour a few necessary vertices to remove the small number of monochromatic edges which remain.

http://www.tau.ac.il/~nogaa/PDFS/Publications/Hypergraphs%20with%20high%20chromatic%20number.pdf