Low degree Nullstellensatz certificates for 3-colorability (Q907253)

Summary: In a seminal paper, \textit{J. De Loera} et. al [in: Proceedings of the 2008 international symposium on symbolic and algebraic computation, ISSAC 2008, Linz/Hagenberg, Austria, July 20--23, 2008. New York, NY: Association for Computing Machinery (ACM). 197--206 (2008; Zbl 1297.05229)] 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 \(\Bbbk\). 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 \(\Bbbk=\mathrm{GF}(2)\). This greatly simplifies the work of De Loera et. al [loc. cit.], 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 \(\Bbbk=\mathrm{GF}(2)\).