The set of all -hereditary properties has been defined in Section 2. We now add ^a to our notation for the set of all additive -hereditary properties.

If we deal with the partitions of the vertices, many partial orders considered preserve the order "to be an induced subgraph" i.e., they have the following property:

O1: If G H then G H .

Let us mention some of them in the following example.

Example 5.

1. H G (to be a subgraph), i.e., a graph H is a subgraph of G,
2. HG (to be an induced subgraph), i.e. H is an induced subgraph of G,
3. H_SG (to be topologically contained), which means that a subdivision of H is a subgraph of G[59],
4. H_MG (to be a minor), i.e., H can be obtained from a subgraph of G by the contractions of someedges of G [18].

Let us remark that _M-hereditary properties are also called minor hereditary (see [18]) and are related to the well-known Hadwiger conjecture, on the other hand, the _S-hereditary properties are involved in Hajós' conjecture [94]. Obviously, both minor hereditary and _S-hereditary properties are hereditary.

Clearly, if satisfies O1 and if P is -hereditary, then P is induced hereditary. Hence in such a case we have that } and that ^{a a}.

Our first result describes the structure of these systems of sets with respect to any partial order on I as ordered systems with respect to inclusion. The proofs are easy and similar results are discussed in [16].

Lemma 57 Let be any partial order on I. Then

1. The intersection of any subset of is a member of .
2. The intersection of any subset of ^a is a member of^a.
3. The union of any subset of is a member of .
4. The union of any directed subset of ^a is a member of ^a.

By the above lemma, is a closure system and ^a is an algebraic closure system (see [47]). We can also define (using parts 1 and 2 of this lemma) for any set G of graphs, the property

[G] = {P : P , G P}

[G]^a = {P : P ^a , G P}

additive - hereditary property generated by

Since [G] is the least -hereditary property containing G in I, we can describe it using only graph theoretical constructions:

[G] = { G : G I, GH for some HG} .

G₁G₂ H₁ H₂

[G]^a = {G : G I, G H for some finite union H of graphs in G} .

The partially ordered sets ( , ) and (^a , ) are lattices. Indeed, by Lemma 57, the meet and join operations of these lattices can be described as follows: If and ^a, then

= and = in ( , )

= and = _^a in (^a, ).

Also, ( , ) and (^a, ) are complete algebraic lattices --- a fact which is trivial for the former. The compact elements of these algebraic lattices are, like for any closure system, the finitely generated elements. We describe this in the following result.

Lemma 58 Let P be an element of ( , ) or of ( ^a , ). Then the following are equivalent

1. P is a compact element of this lattice.
2. P is finitely generated in this lattice.
3. P contains only finitely many pairwise non-isomorphic connected graphs.

The fact that these lattices are algebraic can also be expressed by the statements in the following lemma.

Lemma 59 Let P be any element of ( , ) or of ( ^a , ). Then P is the join of all the compact elements that are smaller than P. In fact:

1. If P , then P = _{G P}} [G].}
2. If P ^a, then P = _{G P}} [G]^a.}

Clearly, is the least element of both lattices ( , ) and (^a , ) while I is the greatest element of them both. Again, as in the case for the lattices of -hereditary sets, ( ^a , ) is not a sublattice of ( , ) since the join of properties in the latter is the union of these properties and it may be a proper subset of the join of these properties in the former. It is also trivial to see that the lattice ( , ) is a distributive lattice.

For lattices of the form (^a , ) we need an extra condition to enable us to imitate the proof of Theorem 5 of [17] which will show that the lattices are distributive. For this we say that a partial order in I is union compatible if every P has the property that for every H I, if HG where G is a union of members of P, then H is equal to a union of members of P. Note that the two partial orders and both have this property. Now we can formulate

Theorem 60 If is a union compatible partial order, then (^a , ) is a distributive lattice.

It is not so difficult to see that also the lattices ^a_S of subdivision hereditary additive properties and ^a_M of minor hereditary additive properties are distributive.

In general the completeness of an (additive) hereditary property P need not be defined. However, we can still define, for a given nonnegative integer k,

_,k = {P : c(P) =k} and

_,k^a = {P ^a : c(P) = k} .

Then we have

Theorem 61 For any nonnegative integer k, the lattice ( _,k , ) is a sublattice of ( , ) and the lattice ( _,k^a , ) is a sublattice of ( ^a , ).

According to the result of Greenwell, Hemminger and Klerlein [48] for any the -hereditary properties can be characterized in terms of forbidden substructures. For example, for the order "to be an induced subgraph" the set of minimal forbidden subgraphs of P we can define as follows: C(P) = { HP : for every v V(G), H - v P}. However it is not always possible to describe properties in terms of minimal forbidden subgraphs in this general context. Let us remark that such a characterization exists if the partial order on I is so called well-founded i.e., every strictly descending chain in (I, ) is finite (see [59]). One can consider also maximal graphs. Let us define, for a -hereditary property P I, the set of -maximal graphs by

M(P) = {G I : G P, and every graph H I satisfying GH, GH does not belong to P}.

It is, however, more natural to weaken the condition for membership of M(P). Recall the resulting set of maximal graphs M(P) (see Section 2).

M(P) = {G I : G P, G+e P for each e E()}.

Related problems have been investigated also in [59] and [83].