School of Mathematics (ETDs)

Permanent URI for this community

https://hdl.handle.net/10539/38013

Browse

Browsing School of Mathematics (ETDs) by Author "Maphakela, Lesiba Joseph"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Chromatic Polynomials and Certain Classes of Graphs
    (University of the Witwatersrand, Johannesburg, 2023) Maphakela, Lesiba Joseph; Mphako-Banda, G.
    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.