Graphs with large girth and chromatic number are hard for Nullstellensatz
From MaRDI portal
Publication:6573006
DOI10.1137/23M1553273zbMATH Open1543.0506MaRDI QIDQ6573006FDOQ6573006
Authors: Julian Romero, Levent Tunçel 
Publication date: 16 July 2024
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Recommendations
- Graph colouring is hard for algorithms based on Hilbert's Nullstellensatz and Gröbner bases
- Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
- A general approach to deriving the \(g\)-good-neighbor conditional diagnosability of interconnection networks
- Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
- Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Combinatorial aspects of algebraic geometry (05E14)
Cites Work
- Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
- Using Algebraic Geometry
- Graph Theory and Probability
- Title not available (Why is that?)
- Ramanujan graphs
- Combinatorial Nullstellensatz
- Sharp Effective Nullstellensatz
- The relative complexity of NP search problems
- Convex relaxations and integrality gaps
- Coloring, sparseness and girth
- On chromatic number of finite set-systems
- Lower bounds for the polynomial calculus
- Title not available (Why is that?)
- Weak orientability of matroids and polynomial equations
- Good degree bounds on Nullstellensatz refutations of the induction principle
- Algèbre linéaire sur $K[X_1,\dots,X_n]$ et élimination
- Recognizing graph theoretic properties with polynomial ideals
- Constructive generation of very hard 3-colorability instances
- Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
- Another Simple Proof of the High Girth, High Chromatic Number Theorem
- A generalized method for proving polynomial calculus degree lower bounds
- Über die vollen Invariantensysteme.
- A comprehensive analysis of polyhedral lift-and-project methods
- Proof Complexity Meets Algebra
- Graph colouring is hard for algorithms based on Hilbert's Nullstellensatz and Gröbner bases
This page was built for publication: Graphs with large girth and chromatic number are hard for Nullstellensatz
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6573006)
