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.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:uj/uj:1780 |
| Date | 06 December 2011 |
| Creators | Dorfling, Michael Jacobus |
| Source Sets | South African National ETD Portal |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0016 seconds