Abstract
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.