Low Degree Nullstellensatz Certificates for 3-Colorability

Bo Li, Benjamin Lowenstein, Mohamed Omar

Abstract

In a seminal paper, De Loera et. al introduce the algorithm NulLA (Nullstellensatz Linear Algebra) and use it to measure the difficulty of determining if a graph is not 3-colorable. The crux of this relies on a correspondence between 3-colorings of a graph and solutions to a certain system of polynomial equations over a field $\mathbb{k}$. In this article, we give a new direct combinatorial characterization of graphs that can be determined to be non-3-colorable in the first iteration of this algorithm when $\mathbb{k}=GF(2)$. This greatly simplifies the work of De Loera et. al, as we express the combinatorial characterization directly in terms of the graphs themselves without introducing superfluous directed graphs. Furthermore, for all graphs on at most $12$ vertices, we determine at which iteration NulLA detects a graph is not 3-colorable when $\mathbb{k}=GF(2)$.

Introduction

Determining if a graph can be colored with just three colors (3-colorability) is a classic NP-complete problem. One modern approach to this challenge is the Nullstellensatz Linear Algebra (NulLA) algorithm. This method translates the graph coloring problem into a system of polynomial equations. If the system has no solutions, the graph is not 3-colorable. The "difficulty" of proving a graph is not 3-colorable in this framework is measured by the Nullstellensatz degree. A low degree means a "certificate" (a mathematical proof of infeasibility) can be found quickly.

Combinatorial Characterization over GF(2)

While previous research established ways to identify graphs with a degree-1 certificate, those methods often relied on complex "superfluous" directed graphs. This paper simplifies the model by focusing on the finite field $GF(2)$ and utilizing Bayer’s formulation to represent graph colorability as polynomials.

The authors define a new property: a graph being "covered by length 2 paths." They prove (Theorem 1.6) that a graph has a degree-1 Nullstellensatz certificate ($N_{\mathbb{k}}(G) = 1$) if and only if it meets this criteria. This involves finding a set of paths of length two that satisfy specific parity conditions regarding how many times edges and vertices appear.

Structural Obstructions and Easy Instances

The paper identifies that certain structures, such as "odd wheels" (a cycle with an odd number of vertices connected to a central hub), always possess a degree-1 certificate, making them computationally "easy" for the NulLA algorithm. Conversely, structural features like the Moser spindle act as obstructions that prevent a graph from having a degree-1 certificate, forcing the algorithm to seek higher-degree proofs.

The Moser spindle, a classic example of a 4-critical graph that requires a higher-degree certificate.

Key Results and Computational Census

To test the limits of the NulLA algorithm, the authors conducted a complete computational census of 4-critical graphs—graphs that are not 3-colorable but become so if any single edge is removed. They analyzed a total of 15,982 graphs with up to 12 vertices.

Census of 4-critical graphs up to 12 vertices, showing the distribution of Nullstellensatz degrees.

As shown in the data, for all graphs with 12 or fewer vertices, the Nullstellensatz degree is at most 4. In their census:

  • 202 graphs had a degree-1 certificate.
  • 15,780 graphs had a degree-4 certificate.
  • No graphs in this range required a degree higher than 4 (notably, degrees must follow the sequence $1, 4, 7 \dots$ due to the underlying algebraic structure).

Conclusion and Future Work

This study demonstrates that for small graphs, the difficulty of proving non-colorability remains remarkably low. However, significant open questions remain. The authors have yet to find a graph requiring a degree higher than 4 for any finite field. Future research may investigate the Hajós construction—a method for building complex 4-critical graphs—to see if these operations can eventually force an "explosion" in Nullstellensatz degree complexity beyond 12 vertices.

Summary updated

Abstract

In a seminal paper, De Loera et. al introduce the algorithm NulLA (Nullstellensatz Linear Algebra) and use it to measure the difficulty of determining if a graph is not 3-colorable. The crux of this relies on a correspondence between 3-colorings of a graph and solutions to a certain system of polynomial equations over a field $\mathbb{k}$. In this article, we give a new direct combinatorial characterization of graphs that can be determined to be non-3-colorable in the first iteration of this algorithm when $\mathbb{k}=GF(2)$. This greatly simplifies the work of De Loera et. al, as we express the combinatorial characterization directly in terms of the graphs themselves without introducing superfluous directed graphs. Furthermore, for all graphs on at most $12$ vertices, we determine at which iteration NulLA detects a graph is not 3-colorable when $\mathbb{k}=GF(2)$.
BibTeX
@article{li2016low,
  author = {Bo Li and Benjamin Lowenstein and Mohamed Omar},
  title = {{Low Degree Nullstellensatz Certificates for 3-Colorability}},
  journal = {Electron. J. Comb.},
  year = {2016},
  doi = {10.37236/5103},
}

Loading related content...

Figure