Chromatic Polynomials and Certain Classes of Graphs
Date
2023
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of the Witwatersrand, Johannesburg
Abstract
The chromatic polynomial of a graph has been widely studied in the literature. The focus of this research is on exploring the chromatic polynomial of specific graphs that result from the application of a join operation. The chromatic polynomial of a graph can be expressed in various forms; power form, tree form, factorial form and cycle form. The expressions in various forms, such as power form, tree form, and factorial form, have been subject to comprehensive investigation. However, it should be noted that the cycle form presents relative gaps that necessitate further exploration. This work builds upon the existing literature by engaging in a discussion of the coefficients of the chromatic polynomial of a graph expressed in cycle form. To achieve this objective, we commence by presenting the general formula of the chromatic polynomial in cycle form. Following this, we introduce an algorithm that computes the chromatic polynomial of a graph in cycle form. Additionally, we outline a method for converting the chromatic polynomial of a graph from its tree form into the cycle form. Furthermore, we determine the values of the first and second terms of the chromatic polynomial in its cycle form. This research also complements the well established knowledge of the chromatic polynomial of graphs resulting from the application of a join operation. Of particular interest, we explore the joins of various classes of graphs, including the join of a null graph, N1 with a graph G, which is known as the vertex join of graph G. Building upon this framework, we extend our analysis to encompass the join of a null graph, N2, with graph G. Similarly, we present results pertaining to the join of a complete graph, Kn, with a graph G. Significantly, we conduct a thorough comparative analysis of the chromatic equivalence class among these derived classes of graphs. Lastly, we discuss the chromatic uniqueness of these derived classes of graphs, alongside introducing variations to these derived graphs by deleting their edges and subgraphs.
Description
A thesis submitted to the School of Mathematics in fulfillment of the requirements for the degree of Doctor of Philosophy School of Mathematics University of the Witwatersrand, Johannesburg 2023
Keywords
Bispoke, Bivertex join, Chromatic polynomial, Chromatically equivalent, Clique separable, Graph invariant, Graph operation, Hamilton cycle, Induced subgraph, UCTD, Join, Repebispoke
Citation
Maphakela, Lesiba Joseph. (2023). Chromatic Polynomials and Certain Classes of Graphs [PhD thesis, University of the Witwatersrand, Johannesburg]. WireDSpace.https://hdl.handle.net/10539/41682