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)$.
@article{10_37236_5103,
author = {Bo Li and Benjamin Lowenstein and Mohamed Omar},
title = {Low degree {Nullstellensatz} certificates for 3-colorability},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {1},
doi = {10.37236/5103},
zbl = {1329.05114},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5103/}
}
TY - JOUR
AU - Bo Li
AU - Benjamin Lowenstein
AU - Mohamed Omar
TI - Low degree Nullstellensatz certificates for 3-colorability
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/5103/
DO - 10.37236/5103
ID - 10_37236_5103
ER -
%0 Journal Article
%A Bo Li
%A Benjamin Lowenstein
%A Mohamed Omar
%T Low degree Nullstellensatz certificates for 3-colorability
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/5103/
%R 10.37236/5103
%F 10_37236_5103
Bo Li; Benjamin Lowenstein; Mohamed Omar. Low degree Nullstellensatz certificates for 3-colorability. The electronic journal of combinatorics, Tome 23 (2016) no. 1. doi: 10.37236/5103
