Menu
The chromatic polynomial captures a good deal of combinatorial information about a graph, describing its acyclic orientations, its all-terminal reliability, its spanning trees, as well as its colorings. Several methods for computing the chromatic polynomial of a graph G construct a computation tree for G whose leaves are “simple” base graphs for which the chromatic polynomial is readily found. Previously studied methods involved base graphs which are complete graphs, completely disconnected graphs, forests, and trees. In this paper, we consider chordal graphs as base graphs. Algorithms for computing the chromatic polynomial based on these concepts are developed, and computational results are presented.