advisor
Prof. Izak Broere
author
Berger, Amelie Julie
2012-01-24T05:33:07Z
2012-01-24T05:33:07Z
2012-01-24
2000
http://hdl.handle.net/10210/4277
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.
en
Graph theory
Lattice theory
Minimal reducible bounds, forbidden subgraphs and prime ideals in the lattice of additive hereditary graph properties
Thesis