Using Thresholds to Compute Chromatic Polynomials

Abstract

An efficient algorithm for computing chromatic polynomials of graphs is presented. To make very large computations feasible, the algorithm combines the dynamic modification of a computation tree with a hash table to store information from isomorphically distinct graphs that occur during execution. The idea of a threshold facilitates identifying graphs that are isomorphic to previously processed graphs. The hash table together with thresholds allow a table look-up procedure to be used to terminate some branches of the computation tree. This table lookup process allows termination of a branch of the computation tree whenever the graph at a node is isomorphic to a graph that is stored in the hash table. The hashing process generates a large file of graphs that can be used to find any chromatically equivalent graphs that were generated. The initial members of a new family of chromatically equivalent graphs were discovered using this algorithm.