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 (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory  15(1) (1995)   11-18
DOI: 10.7151/dmgt.1002

REDUCIBLE PROPERTIES OF GRAPHS

P. Mihók and G. Semanišin

Department of Geometry and Algebra, Faculty of Sciences,
P. J. Šafárik's University
Jesenná 5, 04154 Košice, Slovak Republic

Abstract

Let   L   be the set of all hereditary and additive properties of graphs. For  P1, P2L, the reducible property   R = P1ºP2   is defined as follows:   G ∈ R   if and only if there is a partition   V(G) = V1∪V2   of the vertex set of   G   such that   ⟨V1GP1   and   ⟨V2GP2. The aim of this paper is to investigate the structure of the reducible properties of graphs with emphasis on the uniqueness of the decomposition of a reducible property into irreducible ones.

Keywords: hereditary property of graphs, additivity, reducibility

1991 Mathematics Subject Classification: 05C15, 05C75

References

[1] V. E. Alekseev, Range of values of entropy of hereditary classes of graphs, Diskretnaja matematika 4 (1992) 148-157 (Russian).
[2] M. Borowiecki, P. Mihók, Hereditary properties of graphs in: Advances in Graph Theory, Vishwa International Publication, India, (1991) 42-69.
[3] G. Chartrand, L. Lesniak, Graphs and Digraphs (Wadsworth & Brooks/Cole, Monterey California 1986).
[4] P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: Graphs, Hypergraphs and Matroids (Zielona Góra, 1985) 49-58.
[5] P. Mihók, An extension of Brook's theorem, Annals of Discrete Math. 51 (1992) 235-236.
[6] P. Mihók, On the minimal reducible bound for outerplanar and planar graphs, (to appear).
[7] M. Simonovits, Extremal graph theory, in: L. W. Beineke and R. J. Wilson eds. Selected Topics in Graph Theory 2 (Academic Press, London, 1983) 161-200.
[8] E. R. Scheinerman, On the structure of hereditary classes of graphs, Journal of Graph Theory 10 (1986) 545-551, doi: 10.1002/jgt.3190100414.
[9] E. R. Scheinerman, J. Zito, On the size of hereditary classes of graphs, J. Combin. Theory (B) 61 (1994) 16-39, doi: 10.1006/jctb.1994.1027.