dc.contributor.author Erey, Aysel dc.date.accessioned 2015-08-04T14:12:08Z dc.date.available 2015-08-04T14:12:08Z dc.identifier.uri http://hdl.handle.net/10222/58983 dc.description.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. en_US 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. dc.language.iso en en_US dc.subject Graph Colouring en_US dc.subject Chromatic Polynomial en_US dc.subject Sigma Polynomial en_US dc.subject Roots of Polynomials en_US dc.title An Investigation on Graph Polynomials en_US dc.date.defence 2015-07-27 dc.contributor.department Department of Mathematics & Statistics - Math Division en_US dc.contributor.degree Doctor of Philosophy en_US dc.contributor.external-examiner David Wagner en_US dc.contributor.graduate-coordinator David Iron en_US dc.contributor.thesis-reader Jeannette Janssen en_US dc.contributor.thesis-reader Richard Nowakowski en_US dc.contributor.thesis-supervisor Jason Brown en_US dc.contributor.ethics-approval Not Applicable en_US dc.contributor.manuscripts Yes en_US dc.contributor.copyright-release No en_US
﻿ Find Full text