Nullstellensatz degree under Hajós joins and vertex identifications

Source abstract

We study the minimum coefficient degree $N_{k,\F}(G)$ of a Nullstellensatz certificate for Bayer's $k$-coloring equations, where the characteristic of $\F$ does not divide $k$. If $J$ is a \HJ\ join of non-$k$-colorable graphs $G,H$ and $m=\max\{N_{k,\F}(G),N_{k,\F}(H)\}$, then $N_{k,\F}(J)\leq m+k$. When deletion of the selected edge makes each input $k$-colorable, we also have $N_{k,\F}(J)\geq m$; the degree congruence then gives $N_{k,\F}(J)\in\{m,m+k\}$. This partially answers a question of Li, Lowenstein, and Omar. For three-coloring over $\F_2$, we construct an infinite $4$-critical family of exact degree seven, attaining the bound at input degree four. In contrast, every graph constructed from $K_4$ solely by \HJ\ joins has degree $O(\log n)$ and a certificate with polynomially many terms: joins preserve treewidth at most three, and balanced separators yield low-degree certificates. Additional vertex identifications are excluded from this obstruction. We classify all single identifications of the $25$-vertex base graph; exactly $36$ preserve degree seven, producing $24$-vertex $4$-critical graphs of treewidth four. A compressed self-join at adjacent true twins prevents degree loss and gives a repeatable rule adding four vertices per round. The rule does not establish degree amplification or preservation of criticality. Exact witnesses and standalone verification programs accompany the finite results.