Abstract
M.Sc.
The aim of this thesis is to investigate the topic of edge-colourings of graphs in the
context of hereditary graph properties. We particularly aim to investigate analogues
of reducibility, unique factorization and some related concepts.
Chapter 1 gives the basic definitions and terminology. A few useful general results
are also stated.
In Chapter 2 we define and investigate decomposability, the analogue of reducibility.
Some general results are first proved, such as that the indecomposability of an
additive induced-hereditary property in the lattice of such properties implies that it is
indecomposable in a general sense. The decomposability of various specific properties
is then investigated in the rest of the chapter.
In Chapter 3 we investigate unique decomposability, the analogue of unique factorization.
We give examples showing that not every additive hereditary property
is uniquely decomposable, and we obtain some results on homomorphism properties
which lead to the unique decomposability of Ok. We also consider some related
questions, such as cancellation and preservation of strict inclusions.
Chapter 4 deals with Ramsey properties. We obtain some general results and,
using the so-called partite construction, we obtain a few restricted Ramsey-graph
results. As a corollary, we obtain two more unique decomposability results.
In Chapter 5 we obtain various bounds involving the property Vk of k-degeneracy.
We also investigate the sharpness of these bounds and prove that Vk is indecomposable
for every k.
Chapter 6 deals with the connection between colourings of infinite graphs and
properties of finite graphs. We obtain some extensions of the Compactness Principle
and give an example showing that the Compactness Principle can be useful in studying
finite graphs.