The asymptotic lower-bound conjecture for Nullstellensatz certificates of graph-coloring ideals

Let $\mathbb K$ be a field, let $m$ be a positive integer, and let $G$ be a graph. A Nullstellensatz certificate of the $k$-coloring ideal of $G$ is an identity certifying that $G$ is not $k$-colorable, and its degree is the degree of that certificate.

Asymptotic certificate-degree conjecture. For every field $\mathbb K$ and every positive integer $m$, there exists a constant $k_0$ with the following property: for each $k>k_0$ and every non-$k$-colorable graph $G$, every Nullstellensatz certificate of the $k$-coloring ideal of $G$ has degree at least $mk+1$.

The conjecture proposes that the lower bound on certificate degree grows by an arbitrarily prescribed multiple of the number of colors for sufficiently large $k$. It is motivated by computational evidence that the basic lower bound $N_{k,\mathbb K}(G)\geq k+1$ is not tight for large $k$.