Worst-Case Analysis of Read’s Chromatic Polynomial Algorithm

The worst-case time-complexity of Read’s edge-addition/contraction algorithm for computing the chromatic polynomial of an \(n\)-vertex graph is shown to be \({O}(n^2B(n))\), where \(B(n)\) is the \(n\)th Bell number, which grows faster than \(c^n\) for any \(c\) but slower than \(n!\). The factor \(n^2\) can be reduced to \(n\), and the space-complexity from \({O}(n^3)\) to \({O}(n^2)\), by storing in arrays the information needed to reverse each transformation made on the graph.