Chromatic uniqueness of certain complete tripartite graphs with some edges deleted / Lau Gee Choon and Chu Hong Heng

Since the introduction of the concepts of chromatically unique graphs and chromatically equivalent graphs, many families of such graphs have been obtained. In this thesis, we continue with the search of new families of chromatically unique graphs In Chapter 1, we define the concept of graph colouring, the associated chromatic polynomial and some properties of chromatic polynomial. We also give some necessary conditions for graphs that are chromatically unique or chromatically equivalent. Chapter 2 begins with the definition of complete tripartite graphs and some preliminary results related to complete tripartite graphs. In particular, certain chromatically unique complete tripartite graphs are given. Some new chromatically unique complete tripartite graphs are then presented at the end of this chapter. In Chapter 3, we first give some necessary conditions for complete tripartite graphs with some edges deleted to be chromatically equivalent. We then proved that certain complete tripartite graphs with one edge deleted are also chromatically unique. The determination of the chromaticity of other complete tripartite graphs with certain edges deleted is left as an open problem for future research. We end the thesis by making a conjecture that all complete tripartite graphs with each partite set having at least two
vertices are chromatically unique.