Graphs with large girth and chromatic number are hard for Nullstellensatz

DOI10.1137/23M1553273zbMATH Open1543.0506MaRDI QIDQ6573006FDOQ6573006

Levent Tunçel, Julian Romero

Publication date: 16 July 2024

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

graphs with large girthHilbert's Nullstellensatzgraphs coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Combinatorial aspects of algebraic geometry (05E14)

Cites Work

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

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)