Chromatic polynomials of some derived graphs

Abstract

The chromatic polynomial of a graph, is well known and studied in the literature. Explicit expressions for the chromatic polynomials of some classes of graphs are well known. In addition, formulas for computing the chromatic polynomial of graphs derived from some graph operations are known. Interestingly, chromatic polynomials of graphs can be expressed in different forms, using different classes of graphs. In the literature, chromatic polynomials have been expressed and studied in null graph form, tree form and complete graph form. Although the chromatic polynomial of a graph can also be expressed in cycle graph form, this form has not been studied in great detail in the literature. In this dissertation, we study the chromatic polynomials of some graphs derived from graph operations, namely, the wheel graph and the fan graph. These two graphs are derived from the vertex join of a cycle and a tree, respectively. The chromatic polynomial of a fan graph and a wheel graph found in the literature are factorizations of their null graph form. We studied the chromatic polynomial of a fan graph in cycle form and we found that the coefficients in cycle form result in an array where each row can be computed using the row above. Given this formula for the fan graph, we introduce the fan graph form and express the chromatic polynomial of the wheel graph in this form. We then extend this result to give a method to predict the coefficients of the chromatic polynomial of a wheel graph in cycle form.