{"id":"arxiv/2609.14865","url":"https://arxiv.org/abs/2609.14865","tags":["math.CO","cs.CC"],"score":0,"title":"Nullstellensatz degree under Hajós joins and vertex identifications","domain":"math.CO","source":"arxiv","authors":["Ying Xie"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-14","reactions":{}}