M.Sc. / In this dissertation we study two types of colourings, namely line-distinguishing colourings and harmonious colourings. A line-distinguishing colouring of a graph G is a k-colouring of the vertices of G such that no two edges have the same colour. The line-distinguishing chromatic number G is defined as the smallest k such that G has a line-distinguishing k-colouring. A harmonious colouring of a graph G is a proper k-colouring of the vertices of G such that no two edges have the same colour, i.e. no two adjacent vertices can have the same colour. The harmonious chromatic number hG is defined as the smallest k such that G has a line-distinguishing k-colouring. In Chapter 0 we discuss some of the terminology and definitions used later on in our study. In Chapter 1 we introduce line-distinguishing colourings and consider the line-distinguishing chromatic number of certain familiar classes of graphs such as trees, paths, cycles and complete graphs. We also consider graphs with line-distinguishing chromatic number G equal to the usual chromatic number G, and we compare G with the chromatic index G of a graph. In Chapter 2 we mostly discuss minimal line-distinguishing (MLD) colourings. We consider minimal line-distinguishing colourings and graphs of diameter two as well as classes of regular MLD-colourable graphs. We also introduce the concept of distance regular graphs and discuss minimal line-distinguishing colourings in these graphs. In Chapter 3 we introduce a new parameter, namely the upper line-distinguishing chromatic number H G of a graph. We investigate H G for paths and cycles, and consider graphs with small upper line-distinguishing chromatic numbers. In Chapter 4 we consider the second type of colouring studied in this dissertation, namely harmonious colourings. We define the harmonious chromatic number hG and determine hG for certain classes of graphs such as paths, trees, cycles and complete graphs. In Chapter 5 we discuss upper and lower bound for hG. In Chapter 6 we discuss the upper harmonious chromatic number HG of a graph, and we determine HG for paths and cycles. We also consider graphs satisfying HG G 1. The purpose of this study is to compile a resource which will give a thorough and well-integrated background on line-distinguishing and harmonious colourings. It is also intended to lay the groundwork for further doctoral studies in the field of colourings.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:uj/uj:8248 |
| Date | 31 March 2009 |
| Source Sets | South African National ETD Portal |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0133 seconds