Discussiones Mathematicae Graph Theory 17(1) (1997)
5-50

## A Survey of Hereditary Properties of Graphs

MIECZYSLAW BOROWIECKI

*Institute of Mathematics, Technical University of Zielona
Góra*

Podgórna 50, 65-246 Zielona Góra, Poland

e-mail : m.borowiecki@im.uz.zgora.pl

IZAK BROERE

*Department of Mathematics, Rand Afrikaans University *

P.O. Box 524, Auckland Park, 2006 South Africa

e-mail : ib@rau3.rau.ac.za

MARIETJIE FRICK

*Department of Mathematics, Applied Mathematics and Astronomy *

University of South Africa, P.O. Box 392, Pretoria, 0001 South Africa

e-mail : frickm@alpha.unisa.ac.za

and

PETER MIHÓK

GABRIEL SEMANIŠIN

*Faculty of Sciences, Department of Geometry and Algebra *

P.J. Šafárik University, 041 54 Košice, Slovakia

e-mail : mihok@Košice.upjs.sk

e-mail : semanisin@duro.upjs.sk

## Abstract

In this paper we survey results and open problems on the structure of additive and
hereditary properties of graphs. The important role of vertex partition problems, in
particular the existence of uniquely partitionable graphs and reducible properties of
graphs in this structure is emphasized. Many related topics, including questions on the
complexity of related problems, are investigated.

**Keywords:** hereditary property of graphs, vertex partition, reducible property,
graph invariants, complexity.

**1991 Mathematics Subject Classification:** 05C15, 05C35, O5C75, 03D15, 06B05,
06D05.

**Contents :**

- Introduction and notation
- The lattice of additive and hereditary properties of graphs
- Vertex partitions and reducible properties
- Lattices with respect to other orderings
- Invariants related to hereditary properties
- Complexity results

References

IF YOU HAVE SOME PROBLEMS WITH READING OF THIS DOCUMENT, THEN TRY TO SET YOUR BROWSER
WITH THESE VALUES.

1997