Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture

In this paper we further explore the recently discovered connection by Björklund and Kaski [STOC 2024] and Pratt [STOC 2024] between the asymptotic rank conjecture of Strassen [Progr. Math. 1994] and the three-way partitioning problem. We show that under the asymptotic rank conjecture, the chromatic number of an n-vertex graph can be computed deterministically in O(1.99982 n ) time, thus giving a conditional answer to a question of Zamir [ICALP 2021], and questioning the optimality of the 2 n poly(n) time algorithm for chromatic number by Björklund, Husfeldt, and Koivisto [SICOMP 2009].

Viewed in the other direction, if chromatic number indeed requires deterministic algorithms to run in close to 2 n time, we obtain a sequence of explicit tensors of superlinear rank, falsifying the asymptotic rank conjecture.

Our technique is a combination of earlier algorithms for detecting k-colorings for small k and enumerating k-colorable subgraphs, with an extension and derandomisation of Pratt's tensor-based algorithm for balanced three-way partitioning to the unbalanced case.