  We study the computational efficiency of approaches, based on Hilbert's
Nullstellensatz, which use systems of linear equations for detecting
non-colorability of graphs having large girth and chromatic number. We show
that for every non-$k$-colorable graph with $n$ vertices and girth $g>4k$, the
algorithm is required to solve systems of size at least $n^{\Omega(g)}$ in
order to detect its non-$k$-colorability.
