An Investigation on Graph Polynomials

Abstract

The chromatic polynomial of a graph 𝐺, denoted π (𝐺, 𝑥), is the polynomial whose evaluations at positive integers 𝑥 count the number of (proper) 𝑥-colourings of 𝐺. This polynomial was introduced by Birkhoff in 1912 in an attempt to prove the famous Four Colour Theorem which stood as an unsolved problem for over a century. Since then, the chromatic polynomial has been extensively studied and it has become an important object in enumerative graph theory.

In this thesis, we study the chromatic polynomial and two other related polynomials, namely, the σ-polynomial and the restrained chromatic polynomial. In Chapter 2, we begin with the σ-polynomial. We investigate two central problems on the topic, namely, log-concavity and realness of the σ-roots. In Chapter 3, we focus on bounding the chromatic polynomial and its roots. Chapter 4 is devoted to the restrained chromatic polynomial which generalizes the chromatic polynomial via the restrained colourings. We focus on the problem of determining restraints which permit the largest or smallest number of 𝑥-colourings.