Approximate Graph Colouring And The Hollow Shadow

We show that approximate graph colouring is not solved by constantly many levels of the lift-and-project hierarchy for the combined basic linear programming and affine integer programming relaxation. The proof involves a construction of tensors whose fixed-dimensional projections are equal up to reflection and satisfy a sparsity condition, which may be of independent interest. ABSTRACT We show that approximate graph colouring is not solved by con-stantly many levels of the lift-and-project hierarchy for the com-bined basic linear programming and afine integer programming relaxation.

The proof involves a construction of tensors whose fixed-dimensional projections are equal up to reflection and satisfy a sparsity condition, which may be of independent interest. Abstract. We show that approximate graph coloring is not solved by the lift.

We show that approximate graph colouring is not solved by constantly many levels of the lift. Approximate Graph Colouring and the Hollow Shadow.Lorenzo Ciardo, Stanislav Zivny (University of Oxford). Ciardo, Lorenzo; Živný, Stanislav (2025) Approximate Graph Coloring and the Crystal with a Hollow Shadow.

SIAM Journal on Computing, 54 (4). doi:10.1137/24m1691594. Export Conference item Approximate graph colouring and the hollow shadow Abstract: We show that approximate graph colouring is not solved by constantly many levels of the liftand.

c-colourable graph, where 3 ≤ c ≤ d. There is a huge gap in our understanding of this problem. For an n-vertex graph and c = 3, the best known polynomial-time algorithm of Kawarabayashi, Thorup, and Yoneda [63] finds a d-colouring with d = ̃O(n0.19747), building on.

Among other things, we improve the state-of-the-art in approximate graph colouring by showing that, for any k ≥ 3, it is NP-hard to find a (2 k -1).