AN INVESTIGATION ON GRAPH POLYNOMIALS
Aysel Erey ยท DalSpace (Dalhousie University) ยท 2015
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.