Efficient Computation of Chromatic and Flow Polynomials
Hicks, Illya V
Master of Arts
This thesis surveys chromatic and flow polynomials, and presents new efficient methods to compute these polynomials on specific families of graphs. The chromatic and flow polynomials of a graph count the number of ways to color and assign flow to the graph; they also contain other important information such as the graph's chromatic number, Hamiltonicity, and number of acyclic orientations. Unfortunately, these graph polynomials are generally difficult to compute; thus, research in this area often focuses on exploiting the structure of specific families of graphs in order to characterize their chromatic and flow polynomials. In this thesis, I present closed formulas and polynomial-time algorithms for computing the chromatic polynomials of novel generalizations of trees, cliques, and cycles; I also use graph duality to compute the flow polynomials of outerplanar graphs and generalized wheel graphs. The proposed methods are validated by computational results.
Chromatic polynomial; flow polynomial