Graphs with large girth and chromatic number are hard for Nullstellensatz

2022/12/10 by Romero, Julian, Tunçel, Levent · 1 citation
#Algebraic Geometry (math.AG) #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2212.05365

Abstract

We study the computational efficiency of approaches, based on Hilbert's Nullstellensatz, which use systems of linear equations for detecting non-colorability of graphs having large girth and chromatic number. We show that for every non-k-colorable graph with n vertices and girth g>4k, the algorithm is required to solve systems of size at least n^Ω(g) in order to detect its non-k-colorability.

Cited by

• Lower Bounds for CSP Hierarchies Through Ideal Reduction

Related

• Low Degree Nullstellensatz Certificates for 3-Colorability
• Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases
• Near-colorings: non-colorable graphs and NP-completeness
• Improved Hardness of Approximating Chromatic Number
• b-coloring graphs with large girth