Gr\"obner Bases and Nullstellens\"atze for Graph-Coloring Ideals

arXiv1410.6806MaRDI QIDQ6255779FDOQ6255779

Authors: Jesús A. De Loera, Susan Margulies, Michael Pernpeintner, Eric Riedl, David Rolnick, Gwen Spencer, Despina Stasi, Jon Swenson 

Publication date: 24 October 2014

Abstract: We revisit a well-known family of polynomial ideals encoding the problem of graph-$k$-colorability. Our paper describes how the inherent combinatorial structure of the ideals implies several interesting algebraic properties. Specifically, we provide lower bounds on the difficulty of computing Gr"obner bases and Nullstellensatz certificates for the coloring ideals of general graphs. For chordal graphs, however, we explicitly describe a Gr"obner basis for the coloring ideal, and provide a polynomial-time algorithm.

This page was built for publication: Gr\"obner Bases and Nullstellens\"atze for Graph-Coloring Ideals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6255779)