Ph.D. / After giving basic definitions concerning additive hereditary properties of graphs, this document is divided into three main sections, concerning minimal reducible bounds, minimal forbidden subgraphs and prime ideals. We prove that every irreducible property has at least one minimal reducible bound, and that if an irreducible property P is contained in a reducible property R, then there is a minimal reducible bound for P contained in R. In addition we show that every reducible property serves as a minimal reducible bound for some irreducible property. Several applications of these results are given in the case of hom-properties, mainly to show the existence of minimal reducible bounds of certain types. We prove that every degenerate property has a minimal reducible bound where one factor is the class of edgeless graphs and provide evidence that this may also be true for an arbitrary irreducible property. We also consider edge partitions and we show that the results for minimal decomposable bounds are similar to those for minimal reducible bounds. The second set of results deals with minimal forbidden subgraphs of graph properties. We show that every reducible property has infinitely many minimal forbidden subgraphs since the set of all the cyclic blocks making up these graphs is infinite. Finally we consider the lattice of all additive hereditary properies and study the prime ideals in this lattice. We give an example of a prime ideal that is not co-principal and give some requirements that non co-principal prime ideals should satisfy. 'vVe prove that the set of properties with bounded chromatic number is not a prime ideal by showing that a property P with bounded chromatic number can be written as the intersection of two properties with unbounded chromatic number if and only if P contains all trees.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:uj/uj:1915 |
| Date | 24 January 2012 |
| Creators | Berger, Amelie Julie |
| Source Sets | South African National ETD Portal |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0016 seconds