Nullstellensatz degree bounds affect graph coloring complexity
Nullstellensatz degree under Hajós joins and vertex identifications
Computational Complexity
Summary
The paper studies how complex it is to prove that certain graphs cannot be colored with a set number of colors, using a mathematical tool called the Nullstellensatz. The authors find limits on this complexity when combining graphs in specific ways called Hajós joins and vertex identifications. They show examples of graphs that reach these limits and classify particular operations that preserve this complexity measure. Their results help understand the difficulty of coloring graphs and provide exact certificates for these proofs.
What this means in practice
- •For graph algorithm developers: Improve algorithms for verifying non-colorability of graphs by using low-degree certificates from Hajós joins and vertex identification classifications.
- •For combinatorial optimization engineers: Use exact degree bounds on coloring certificates to guide construction of test instances that challenge graph coloring heuristics.
A theory result. No direct application yet.
Authors
Ying Xie
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.