Faster Exact Algorithms for 3- and 4-Coloring: Deterministic Improvements and Further Randomized Speedups

We study exact exponential-time algorithms for 3- and 4-coloring. For 3-coloring, the best previously published running-time bound is O^*(1.3289ⁿ), due to Eppstein (SODA 2001). We improve this bound to O^*(1.3204ⁿ) deterministically and O^*(1.3159ⁿ) using randomization. For 4-coloring, the best previously known running-time bound is O^*(1.7159ⁿ), due to Wu, Gu, Jiang, Shao, and Xu (ESA 2024). We improve this bound to O^*(1.6975ⁿ) deterministically and O^*(1.6933ⁿ) using randomization. Our algorithms for both problems combine constraint satisfaction algorithms with dynamic programming over tree and path decompositions, exploiting their complementary strengths on different graph structures. For 6-coloring, the best published randomized running-time bound is exponentially smaller than the best published deterministic bound. For 3- and 4-coloring, however, no such improvement through randomization was previously known. To the best of our knowledge, our results provide the first randomized running-time bounds for these two problems that exponentially improve upon the best previously published deterministic bounds. This raises the question of whether randomization offers an inherent exponential advantage for 3- and 4-coloring.