What did we do?

We present piecewise analysis, a new general method that analyzes the running time of branching algorithms.

What did we get?

• We reanalyze two 17-year-old algorithms from Fomin et al. [2007] that solve 4-Coloring and #3-Coloring respectively and improve the analysis of both.

• We obtain a new running time O(1.7215^n) upper bound for 4-Coloring, which is the first improvement in the best known running time since 2007.