Approximate Graph Colouring and the Crystal with a Hollow Shadow

2022/11/06 by Ciardo, Lorenzo, Živný, Stanislav · 2 citations
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2211.03168

Abstract

We show that approximate graph colouring is not solved by the lift-and-project hierarchy for the combination of linear programming and linear Diophantine equations. The proof is based on combinatorial tensor theory.

Cited by

• New Obstacles to Multiple Recurrence
• Lower Bounds for CSP Hierarchies Through Ideal Reduction

Related

• Approximate Graph Colouring and Crystals
• Diophantine approximation and coloring
• Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases
• Generalized list colouring of graphs
• Greedy Graph Colouring is a Misleading Heuristic