Graph-Coloring Ideals

DOI10.1145/2755996.2756639zbMath1345.68154OpenAlexW1995921851MaRDI QIDQ2819750

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

Publication date: 29 September 2016

Published in: Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2755996.2756639

zbMATH Keywords

Gröbner basisgraph coloringNullstellensatzinapproximabilityinfeasibility certificatecoloring ideal

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Random sampling in computational algebra: Helly numbers and violator spaces ⋮ On vanishing sums of roots of unity in polynomial calculus and sum-of-squares ⋮ On the robust hardness of Gröbner basis computation ⋮ Privacy-preserving data splitting: a combinatorial approach ⋮ Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach

This page was built for publication: Graph-Coloring Ideals