Low degree Nullstellensatz certificates for 3-colorability

zbMath1329.05114arXiv1503.04680MaRDI QIDQ907253

N. E. Zubov

Publication date: 25 January 2016

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.04680

zbMATH Keywords

polynomial equations over a field \(\mathbb{k}\)

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Unnamed Item
• Unnamed Item
• Stable sets and polynomials
• Recognizing graph theoretic properties with polynomial ideals
• Constructive generation of very hard 3-colorability instances
• Global Optimization with Polynomials and the Problem of Moments
• Theta Bodies for Polynomial Ideals
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility

This page was built for publication: Low degree Nullstellensatz certificates for 3-colorability