Discussiones Mathematicae Graph Theory 17(1) (1997)
5-50
DOI: https://doi.org/10.7151/dmgt.1037
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.
- 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
Contents :
IF YOU HAVE SOME PROBLEMS WITH READING OF THIS DOCUMENT, THEN TRY TO SET YOUR BROWSER WITH THESE VALUES.
1997
Close