Approximate Graph Coloring and the Crystal with a Hollow Shadow
Lorenzo Ciardo, Stanislav Živný · SIAM Journal on Computing · 2025
Abstract. We show that approximate graph coloring 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.