Asad Ullah Khalid

• The chromatic polynomial is a polynomial in a single variable, associated with a graph, that expresses the number of different ways a graph can be properly colored given the number of specified colors. We give the definitions for the vertex coloring of a graph, the chromatic number and formally define the chromatic polynomial. In addition, we define the chromatic polynomial via the partition properties of a graph. We list down the chromatic polynomial for special graphs and discuss a number of reduction schemes, shortcuts, and graph properties that may help to simplify graphs and efficiently compute the chromatic polynomial. We look at the properties of chromatic polynomials that can be used to identify the correctness of our results. We introduce our implementation of a Python program that computes the chromatic polynomial of any graph. The program comprises of different procedures that apply many reduction techniques discussed in this thesis. Finally, we provide a detailed justification of all the methods that we use in our program including a thorough analysis of our code containing examples of increasing complexity and practical run time results.