Graph colouring is hard for algorithms based on Hilbert's Nullstellensatz and Gröbner bases
From MaRDI portal
Publication:5111132
Recommendations
- A general approach to deriving the \(g\)-good-neighbor conditional diagnosability of interconnection networks
- Graph-coloring ideals: Nullstellensatz certificates, Gröbner bases for chordal graphs, and hardness of Gröbner bases
- Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
- Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
- Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
Cited in
(11)- A general approach to deriving the \(g\)-good-neighbor conditional diagnosability of interconnection networks
- On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
- Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
- Limitations of algebraic approaches to graph isomorphism testing
- Proof Complexity Meets Algebra
- Low degree Nullstellensatz certificates for 3-colorability
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
- Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
- Graphs with large girth and chromatic number are hard for Nullstellensatz
- Graph-coloring ideals: Nullstellensatz certificates, Gröbner bases for chordal graphs, and hardness of Gröbner bases
This page was built for publication: Graph colouring is hard for algorithms based on Hilbert's Nullstellensatz and Gröbner bases
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111132)
