Let be arbitrary hereditary properties of graphs. A vertex ()-partition of a graph G is a partition {V₁, V₂, ..., V_n} of V(G) such that for each i=1,2,...,n the induced subgraph G[V_i] has the property P_i (for convenience, the empty set will be regarded as the set inducing the subgraph with any property P).

A property R = is defined as the set of all graphs having a vertex ()-partition. It is easy to see that if are additive and hereditary, then R = is additive and hereditary, too. If P₁ = P₂ = . . . = P_n = P , then we write Pⁿ = .

Thus, e.g., O^k, k 2 denotes the class of all k-colourable graphs, and D₁^k --- the class of graphs with vertex-arboricity at most k.

An additive hereditary property R is said to be reducible in ^a if there exist nontrivial additive hereditary properties P , Q such that R =P Q and irreducible in ^a, otherwise.

If R = P Q we say P and Q divide R. The next lemma, which determines the completeness of reducible hereditary properties follows straightforward from the definitions.

Lemma 23([17], [70]) For any reducible property R = P₁ P₂

3.1 Minimal Reducible Bounds

It is not hard to see ([9], [57]) that for all p,q 0,

O_p+q+1 O_p O_q and D_p+q+1 D_p D_q.

The well-known Theorem of Lovász states.

Theorem 24[65] For p,q 0, holds the following

S_p+q+1 S_p S_q.

Let us remark that, in spite of its very similar nature, the analogous question for W_k still remains open.

Problem 1 Is it true that W_p+q+1 W_p W_q for all p,q 0 ?

Bollobás and Manvel proved the following refinement of Brooks' Theorem.

Theorem 25[4] Let p,q 1 satisfies pq > 1, then

S_p+q I_p+q-1 (D_p-1 S_p) (D_q-1 S_q).

In connection with the Four Colour Problem different types of partitions of the vertices of graphs have been investigated. A short survey of reducible bounds for the class T₃ of planar graphs is given in [11]. Let us recall some of them.

The Four Colour Theorem ([1]) T₃ O⁴ implies

T₃ (O² T₃)² and T₃ O (O³ T₃).

Improving the bound T₃ O D₁² ([10],[51],[90]) Thomassen [93] proved the conjecture of Borodin [9]:

T₃ D₁ (D₂ T₃) and that T₃ C₃ C₃,

where C₃ = {G I : each cycle in G has length 3}.

Another type of bound was proved by Poh [82] and independently by Goddard [45]:

T₃ (D₁ S₂) (T₃ (D₁ S₂)²).

In order to compare these results; the notion of a minimal reducible bound has been introduced (see [57],[71]).

For a given irreducible property P, a reducible property R is called minimal reducible bound for P if P R and there is no reducible property R' R satisfying P R '. In other words, R is a minimal reducible bound for P in ^a if in the interval (P , R) of the lattice ^a there are only irreducible properties. This means that the corresponding "theorem" is sharp and in some sense cannot be improved. The set of all minimal reducible bounds for P will be denoted by B(P). It is worth to pointing out that B(P) might be also empty.

The problem of finding all minimal reducible bounds for the class of planar graphs, formulated by Mihók and Toft in 1993 (see Problem 17.9 in [57]), seems to be very difficult. Some partial results are presented in [11]. For example, in [71] it has been proved that the class of all outerplanar graphs T₂ has exactly two minimal reducible bounds. On the other hand, the set of all minimal reducible bounds of the set of all 1-non-outerplanar graphs is infinite (see [11], [14]).

There are many possible difficulties in proving the minimality of reducible bound for a property P in ^a, let us present some of them. The detailed proofs of the corresponding theorems can be found in [11],[66].

The set B(P) of all minimal reducible properties for P in ^a can be determined for many properties of small completeness using the knowledge of the structure of reducible properties. Let us start with some easy examples.

The property O², the smallest reducible property in ^a and the only reducible property of completeness 1, is obviously the unique minimal reducible bound for P if and only if P O². Hence,

The structure of the reducible properties with completeness 2 follows from the next more general result.

Theorem 26[73] Let P be an additive degenerate hereditary property. Let P₁, P₂ be any additive hereditary properties. Then P P₁ P P₂ if and only if P₁ P₂.

As a corollary, using Lemma 23, we can describe the structure of ₂ = { R: R is a reducible property with c(R) = 2}.

Corollary 27 The set ₂ = {R: R = O P, c(P) = 1} of reducible properties of the completeness 2 partially ordered by set-inclusion forms a lattice isomorphic to ^a₁.

The following result states that one implication of Theorem 26 holds in general.

Theorem 28[73] Let P be a hereditary property of graphs. If P₁, P₂ are any hereditary properties such that P₁ P₂, then P P₁ P P₂.

Combining the facts mentioned above, we obtain the following minimal reducible bounds:

B(O₂) = B(S₂) = B(W₂) = {O O₁}.

The fact that the class of 2-degenerate graphs D₂ has exactly one minimal reducible bound R = O D₁ follows from the construction of Broere (see [11]) which implies

Theorem 29 Let T be any tree and T F(P). Then there exists a planar 2-degenerate graph G which has no vertex (P, P)-partition.

This theorem implies that if a class P contains the class of all 2-degenerate planar graphs and R = P₁ P₂ is a reducible bound for P, then at least one of the factors P_i, (i {1,2}), contains the class D₁ of all forests.

Theorem 29 also generalizes the result of Cowen, Cowen and Woodall [31] which states that there is no positive integer k such that the class of all planar graphs has the bound S_k².

Let us remark that the construction used in the proof of Theorem 29 gives in general non-outerplanar graphs. Thus for the class of outerplanar graphs we may have more reducible bounds. In [71] it has been proved that B(T₂) = {O D₁, (D₁ S₂)²}.

Surprisingly, the minimal reducible bounds for the properties I_k, k = 1,2, ... are trivial and they follow from a result of Nesetril and Rodl.

Theorem 30[78] Let F(P) be a finite set of 2-connected graphs. Then for every graph G of property P there exists a graph H of property P such that for any partition {V₁,V₂ of V(H) there is an i, i=1 or i=2, for which the subgraph H[V_i] induced by V_i in H contains G.

Corollary 31([66]) Let F(P) be a finite set of 2-connected graphs, then the property P has exactly one minimal reducible bound R = O P.

By the Corollary 31 we have, that for any k1, the property I_k has the only minimal reducible bound O I_k i.e., B(I_k) = {O I_k}.

Since the structure of reducible properties of completeness c(R)3 is very complicated (see [74]) there are only some partial results on rather simple properties with completeness 3 (see [11],[66]). The proofs of these results are based on the following lemma.

Lemma 32[11] Let P₁, P₂ be additive degenerate hereditary properties and P₃ P₄ P₁ P₂ for P_i ^a, i=1,2,3,4. Then P₃ P₁ and P₄ P₂ or P₃ P₂ and P₄ P₁.

Using Lemma 32 and Lemma 23 we obtain:

Theorem 33([66]) For any positive integer k,

B(O_k) = {O_p O_q : p+q+1 = k}.

For the class of k-degenerate graphs D_k we can prove

Theorem 34[65] For any positive integer k,

B(D_k) = {D_p D_q : p + q + 1 = k }

In general, in order to prove that B(P) = {R_i : i I}, it is sufficient to verify the following steps:

(i) to verify that R_i is a reducible bound for P, i I,
(ii) to verify that the set of reducible properties {R_i : i I} is an antichain in ^a,
(iii) to verify that there is no reducible property in the interval (P, R_i) for each i I,
(iv) to prove that, if P R for some reducible property {R}, then there exists an iI such that R_i R .

Let us remark, that step (ii) is a straightforward consequence of step (iii) provided that the reducible properties one considers are pairwise distinct.

An effort to verify the steps may be met with resistance of different kinds (see [11],[66]). In order to get over these difficulties, more information on the structure of reducible properties in ^a is necessary. We therefore present some results on the structure of reducible properties in the sequel.

3.2 Which Properties are Reducible?

The structure of minimal forbidden subgraphs for any reducible property R O² is very complicated. There are many partial results to support the conjecture that, for any reducible property R ^a, the set F(R) of minimal forbidden subgraphs for R is infinite (see [68],[69]). Some other results on the structure of F(R), for example, the generalization of the famous Gallai's theorem, are presented in [17] (see also Section 5).

The relationship between the structure of minimal forbidden subgraphs and maximal graphs for a reducible property, by Theorem 18, leads to the following interesting result.

Theorem 35([72]) If P₁ and P₂ are arbitrary hereditary properties of graphs then

(P₁ P₂) = (P₁)+ (P₂)-1.

The graphs maximal with respect to reducible properties have the following structure.

Theorem 36([21],[24]) A graph G is -maximal if and only if for every vertex ()-partition {V₁, V₂, ..., V_n} of V(G)it holds

and the graphs G[V_i], i=1,2, ..., n, are P_i-maximal.

On the other hand, the join of any P_i-maximal graphs need not to be -maximal (see [21],[62]).

From Theorem 36 we immediately have

Theorem 37 If P ^a and there exists an indecomposable P-maximal graph, then the property P is irreducible.

Example 4. Since there exist indecomposable I_k-maximal graphs for any k0, the property I_k is irreducible for each k0.
It is not difficult to find indecomposable P-maximal graphs for any degenerate property P ^a, so that all degenerate properties are irreducible. This fact also follows from Theorem 35.

In the next sections we will present more results supporting the following conjecture.

Conjecture 38 An additive hereditary property P is irreducible if and only if there are indecomposable P-maximal graphs.

3.3 Uniquely Partitionable Graphs

A graph G is said to be uniquely ()-partitionableif G has exactly one (unordered) vertex ()-partition. The set of all uniquely ()-partitionable graphs will be denoted by U().

Thus, e.g., U(Oⁿ) denotes the set of all uniquely n-colourable graphs (see [5],[27],[52]); U(S_kⁿ) denotes the set of so-called uniquely (m,k)-colourable graphs (see [38],[39],[103]); U(W_kⁿ) has been studied in [38],[2]; U(D_kⁿ) in [6],[85] and U(I_kⁿ) in [19],[38], respectively.

Another generalization of uniquely colourable graphs has been introduced by Zhu in [104].

The basic properties of uniquely Pⁿ-partitionable graphs have been investigated e.g., in [6],[38],[69]. Let us recall some necessary conditions for the existence of uniquely ()-partitionable graphs.

Theorem 39([24]) If one of the following holds:

1. P divides Q,
2. Q divides P,
3. there exists S such that S divides both P and Q,

then U(P Q)=.

Let GP. We say that G is P-strict if G+K₁ P.

Theorem 40([20],[24]) Let G be a uniquely ()-partitionable graph and let {V₁,V₂,... ,V_n} be the unique ()-partition of V(G), n2. Then

1. GP₁ P₂ . . . P_j-1 P_j+1 . . . P_n, for every j=1,2,... ,n,
2. the subgraphs G[V_i] are P_i-strict, i=1,2,... ,n,
3. for {i₁,i₂,... ,i_k}{1,2,... ,n} the set V_i1 V_i2... V_ik induces a uniquely (P_i1 P_i2 . . . P_ik)-partitionable subgraph of G,
4. (G) (P_i),
5. |V(G)| (c(P_i)+2)-1,
6. the graph G=G[V₁]+G[V₂]+ . . .+G[V_n] is uniquely ()-partitionable.

Theorem 41([69]) If H and U(), then H is an induced subgraph of some uniquely ()-partitionable graph G.

Many partial result concerning the existence of uniquely Pⁿ-partitionable graphs for different types of properties P can be generalized. For example, the next theorem implies that the bound in (5) of Theorem 40 is sharp for many properties including O_k, S_k and W_k, k 1.

Theorem 42([20]) Suppose are additive hereditary properties such that F(P_i) contains some tree T_i of order c(P_i)+2. Then there exists a uniquely ()-partitionable graph G with

|V(G)| = (c(P_i)+2)-1.

On the other hand for the properties I_k we have

Theorem 43([20]) If G is a uniquely (I_k1, I_k2, . . ., I_kn)-partitionable graph and k_nk_i for i=1,... , n, then

|V(G)|(2k_i+3)+k_n+1,

with equality only if G=+. . . + +K_kn+1.

In [69] the fact that degenerate properties are irreducible is proved by a construction of a uniquely (P ,P)-partitionable graph for an arbitrary degenerate property P ^a. This result can be generalized to

Theorem 44[24] Let , n2, be any degenerate additive and hereditary properties of graphs. Then there exists a uniquely ()-partitionable graph.

Trying to prove that the necessary conditions for the existence of uniquely (P, Q)-partitionable graphs given by Theorem 39 are also sufficient we succeeded in proving it for degenerate properties. The divisibility condition contained in the following definition leads to Theorem 46.

Let P,Q be hereditary properties of graphs and let GP. If S is a subset of the vertex set V(G) such that G[S] Q and for every graph TQ the graph T+(G-S)P, then S is said to be (Q,P)-extendable set of G.

Recall that Q divides P in if there exists a property P^* such that P = Q P^*.

Theorem 45[24] Let P,Q be additive hereditary properties of graphs. Then Q divides P in if and only if every P-maximal graph contains a (Q,P)-extendable set.

Theorem 46[24] Let P,Q ^a and let Q be a degenerate property. Then U(QP) if and only if Q does not divide P in .

The following conjecture (if true) would play an important role in characterizing reducible properties.

Conjecture 47 Let R= , n 2 be a factorization of a reducible property R ^a into irreducible factors. Then U(). In particular, U() if and only if P is irreducible.

In the next section we will show that this conjecture is true for hom-properties.

3.4 Structure of Reducible Hom-Properties

GG'

GC(G)

Hom-properties can be given in various ways, for example, the property C₆ is the same as the property C₃₈. A standard way is to describe a hom-property by a core.

Proposition For any graph H, its core C(H) generates H.

Thus, writing H we assume H be a core.

We have mentioned in Section 2 that it is very difficult to characterize the set of forbidden graphs for hom-properties. Fortunately, this is not the case for the set of maximal graphs with respect to hom-properties. In order to characterize their structure we need to introduce the following concepts and notation.

For any graph G I with a vertex set V(G) = {v₁, v₂, ... , v_n}, we define a multiplication G^:: of G in the following way:

1. V(G^::)=W₁ W₂ ... W_n,
2. for each 1 i n : |W_i| 1,
3. for any pair 1 i < j n: W_i W_j=,
4. for any 1 i j n, u W_i, v W_j: {u,v} E(G^::) if and only if {v_i,v_j} E(G).

Theorem 49[62] A graph G is ( H)-maximal if and only if G is a multiplication of a graph H such that

1. is a core,
2. it is (H)-maximal, and
3. |W_i|=1 for every vertex v_i V() for which there exists a homomorphism : H and a vertex y V(H)-V(()) such that the closed ()-neighborhood of (v_i) is contained in the H-neighborhood of y.}

Corollary 50[62] Let H be a hom-property. Then any multiplication H^:: of the core H is a (H)-maximal graph.

Theorem 49 and Corollary 50 implies that the set of all multiplication of a core H generates the (additive) hereditary property H.

It follows from Theorem 49 that neither join of maximal graphs with respect to hom-properties has to be a maximal graph with respect to the composition of these properties. The next result provides one type of sufficient condition.

Corollary 51[62] If G^:: is a multiplication of a core G and H^:: is a multiplication of a core H, then G^::+H^:: belongs to M(( G) ( H)).

The reducibility of hom-property H is given by the structure of H.

Theorem 52[61] Let a graph H be a core. A hom-property H is irreducible if and only if H is indecomposable.

It is easy to see that any multiplication of an indecomposable graph is indecomposable, too. Hence, by Theorem 49 we obtained for hom-properties an affirmative answer to Conjecture 38.

Theorem 53 A hom-property H is irreducible if and only if every ( H)-maximal graph is an induced subgraph of an indecomposable ( H)-maximal graph.

Since the decomposition of a decomposable graph into the join of indecomposable graphs is unique, the factorization of reducible hom-properties into irreducible hom-properties is also unique. It was proved that this factorization is unique also in ^a:

Theorem 54[61] Let a core H = H₁+H₂+ . . . + H_n be the join of indecomposable graphs H_i, i=1,2,...,n. Then H = ( H₁) ( H₂) . . . ( H_n) is the unique factorization of H into irreducible factors in ^a, apart from the order of the factors.

Let us remark that any multiplication of the core H = H₁+H₂+ . . . + H_n with H_i indecomposable for i = 1,2, ...,n is uniquely ( H₁) ( H₂) ... ( H_n)-partitionable which gives for hom-properties the affirmative answer to Conjecture 47.

The characterization of decomposable cores follows from Theorem 54:

Theorem 55[61] Let the graph H = H₁+H₂+ . . . +H_n be the join of indecomposable graphs H_i, i=1,2, ... ,n. Then the graph H is a core if and only if each H_i is a core for i=1,2, ... ,n.

3.5 Factorization into Irreducible Properties

Conjecture 56 Let R ^a be a reducible property of graphs and R= , n2, be a factorization of R into irreducible factors. Then the factorization is unique (apart from the order of factors).

By Theorem 54 the answer is affirmative for hom-properties. In [74] the unique factorization of all additive and hereditary properties of completeness at most three has been proved. It turns out, that Theorem 35 provides an important contribution to the solution of the mentioned general problem. Indeed, it yields the unique factorization of the product of two degenerate additive hereditary properties.

Some related questions on cancellation in ^a have been investigated in [73].