Contents ... Next ... References

A Survey of Hereditary Properties of Graphs

1. INTRODUCTION AND NOTATION

All graphs considered are finite, simple, i.e., undirected, loopless and without multiple edges. For undefined concepts we refer the reader to [29], [8] and [17].

A graph property is a any isomorphism-closed subclass of graphs. Since we have in general no reason to distinguish between isomorphic copies of a graph, we use the notation I to denote the set of all unlabelled graphs. Therefore, by saying that H is a subgraph of G, we mean that H is isomorphic to a subgraph of G.

If P is a subset of I, then P will also denote the property that a graph is a member of the set P. We shall use the terms set of graphs and property of graphs interchangeably. The symbol will stand for the empty property, i.e. the subsets of I containing no graphs. Properties I and are called trivial.

By the join G₁ + G₂ + ... + G_n of n graphs G₁, G₂, ... ,G_n we mean the graph consisting of disjoint copies of G₁, G₂, ... ,G_n and all the edges between V(G_i) and V(G_j) for all ij. Every graph which is the join of at least two graphs is called decomposable. A graph that is not decomposable is called indecomposable. It is easy to see that a graph G is decomposable if and only if its complement is not connected. Then G is a join of the complements of the components of . Thus every decomposable graph G can be expressed in a unique way as the join of indecomposable graphs.

A homomorphism of a graph G to a graph H is a mapping f of the vertex set V(G) into V(H) which preserves the edges, i.e., if e={u,v} E(G) than f(e)={f(u),f(v)}E(H).

If a homomorphism of G to H exists, we say that G is homomorphic to H and write GH. It is easily seen that in such case for the chromatic number the following inequality (G)<=(H) holds.

A property P is called additive if for each graph G all of whose components have property P it follows that GP too. Throughout the paper we let be a partial order on the set I. A property P is said to be -hereditary if, whenever GP and HG, then also HP. A property P is induced hereditary if it is -hereditary with respect to the relation to be an induced subgraph and P is hereditary if it is -hereditary with respect to the relation to be a subgraph (some authors prefer the term monotone instead of hereditary, see [26], [82]). In the first three sections of this survey we shall concentrate on additive hereditary properties; properties that are hereditary with respect to other partial orderings are the subject of study in later sections.

Hereditary properties were studied extensively (see e.g. [7], [17], [23], [25], [26], [48], [64], [83] and [101]).

Example 1. We list some important hereditary properties, using partially the notation of [17].

	O	=	{GI : G is edgeless, i.e. E(G) = },
	Ok	=	{GI : each component of G has at most k+1 vertices },
	Sk	=	{GI : the maximum degree (G)<= k },
	Wk	=	{GI : the length of the longest path in G is at most k },
	Dk	=	{GI : G is k-degenerate, i.e. the minimum degree (H)<= k for each h G },
	Tk	=	{GI : G contains no subgraph homeomorphic to Kk+2 or K. },
	Ik	=	{GI : G does not contain Kk+2},
	H	=	{GI : G is homomorphic to a given graph H}.

It is easy to see that for k=1 the properties O₁, S₁ and W₁ are equal each other.

Let P be a nontrivial hereditary property. Then there is a nonnegative integer c(P) such that K_c(P)+1P but K_c(P)+2P -- it is called the completeness of P. Obviously

c(O_k) = c(S_k) = c(W_k) = c(D_k) = c(T_k) = c(I_k) = k

and c(P) = 0 if and only if P=O.

By a partition of a set S into n parts we mean an unordered family { S₁, S₂, ... , S_n } of pairwise disjoint subsets of S with S_i = S. Note that some of the S_i's may be empty. In the case that an ordered partition is required we shall denote the ordered partition by [S₁, S₂, ... , S_n].

In Section 2 we investigate the lattice of additive and hereditary properties of graphs. It is shown how minimal forbidden subgraphs and maximal graphs are used to characterize properties.

In Section 3 we discuss vertex partitions of graphs. Reducibility of properties plays a major role in this section and the relationship between this concept and the existence of uniquely partitionable graphs is explained. The concept of minimal reducible bounds are shown to provide a wealth of difficult problems.

In Section 4 lattices arising from other partial orderings on I are studied. These lattices can be used to explain many seemingly unrelated concepts and results from Graph Theory.

Section 5 is devoted to show how many known invariants of graphs can be related to chains of such properties of graphs.

In Section 6 we list some important results concerning the complexity of partition problems related to properties of graphs (see also [98]).

1997