Chromatic number in $19999^n$ time? Fast deterministic set partitioning under the asymptotic rank conjecture
<|reference_start|>Chromatic number in $19999^n$ time? Fast deterministic set partitioning under the asymptotic rank conjecture: In this paper we further explore the recently discovered connection by Bj\"{o}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\operatorname{poly}(n)$ time algorithm for chromatic number by Bj\"{o}rklund, Husfeldt, and Koivisto [SICOMP 2009].   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.<|reference_end|>
@article{björklund2024chromatic,
    title={Chromatic number in $1.9999^n$ time? Fast deterministic set partitioning
  under the asymptotic rank conjecture},
    author={Andreas Bj"orklund, Radu Curticapean, Thore Husfeldt, Petteri Kaski,
  and Kevin Pratt},
    journal={arXiv preprint arXiv:2404.04987},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.04987},
    primaryClass={cs.DS}
}