Abstract
D. Phil (Mathematics)
In this thesis we investigate generalized chromatic numbers in the context of hereditary
graph properties. We also investigate the general topic of invariants of graphs as well as
graph properties.
In Chapter 1 we give relevant definitions and terminology pertaining to graph properties.
In Chapter 2 we investigate generalized chromatic numbers of some well-known additive
hereditary graph properties. This problem necessitates the investigation of reducible
bounds. One of the results here is an improvement on a known upper bound for the path
partition number of the property Wk. We also look at the generalized chromatic number
of infinite graphs and hereby establish the connection between the generalized chromatic
number of properties and infinite graphs.
In Chapter 3 the analogous question of the generalized edge-chromatic number of some
well-known additive hereditary properties is investigated. Similarly we find decomposable
bounds and are also able to find generalized edge-chromatic numbers of properties using
some well-known decomposable bounds.
In Chapter 4 we investigate the more general topic of graph invariants and the role
they play in chains of graph properties and then conversely the invariants that arise from
chains of graph properties. Moreover we investigate the effects on monotonicity of the
invariants versus heredity and additivity of graph properties.
In Chapter 5 the general topic of invariants of graph properties defined in terms of
the set of minimal forbidden subgraphs of the properties is studied. This enables us to
investigate invariants so defined on binary operations between graph properties.
In Chapter 6 the notion of natural and near-natural invariants are introduced and
are also studied on binary operations of graph properties. The set of minimal forbidden
subgraphs again plays a role in the definition of invariants here and this then leads us to
study the completion number of a property.