DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory  17(1) (1997)   5-50
DOI: 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.


    Contents :

  1. Introduction and notation
  2. The lattice of additive and hereditary properties of graphs
  3. Vertex partitions and reducible properties
  4. Lattices with respect to other orderings
  5. Invariants related to hereditary properties
  6. Complexity results

    References


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


1997