ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

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


Discussiones Mathematicae Graph Theory 19(2) (1999) 167-174
DOI: 10.7151/dmgt.1093


Izak Broere and Samuel John Teboho Moagi

Department of Mathematics
Faculty of Science, Rand Afrikaans University
P.O. Box 524, Auckland Park, 2006 South Africa

Peter Mihók

Mathematical Institute, Slovak Academy of Sciences
Gresákova 6, Košice, Slovak Republic
e-mail: mihok@Koš

Roman Vasky

Department of Geometry and Algebra
Faculty of Science, P.J. Safárik University
Jesenná 5, 041 54 Košice, Slovak Republic



A property of graphs is any isomorphism closed class of simple graphs. For given properties of graphs P1,P2,...,Pn a vertex (P1, P2, …,Pn)-partition of a graph G is a partition {V1,V2,...,Vn} of V(G) such that for each i = 1,2,...,n the induced subgraph G[Vi] has property Pi. The class of all graphs having a vertex (P1, P2, …,Pn)-partition is denoted by P1ºP2º…ºPn. A property ℜ is said to be reducible with respect to a lattice of properties of graphs L if there are n ≥ 2 properties P1,P2,...,PnL such that ℜ = P1ºP2º…ºPn; otherwise ℜ is irreducible in L. We study the structure of different lattices of properties of graphs and we prove that in these lattices every reducible property of graphs has a finite factorization into irreducible properties.

Keywords: factorization, property of graphs, irreducible property, reducible property, lattice of properties of graphs.

1991 Mathematics Subject Classification: 05C15, O5C75.


[1] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, Survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037.
[2] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishwa International Publication, Gulbarga, 1991), 42-69.
[3] A. Haviar and R. Nedela, On varieties of graphs, Discuss. Math. Graph Theory 18 (1998) 209-223, doi: 10.7151/dmgt.1077.
[4] R.L. Graham, M. Grötschel and L. Lovász, Handbook of combinatorics (Elsevier Science B.V., Amsterdam, 1995).
[5] T.R. Jensen and B. Toft, Graph colouring problems (Wiley-Interscience Publications, New York, 1995).
[6] P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: M. Borowiecki and Z. Skupień, eds., Graphs, hypergraphs and matroids (Zielona Góra, 1985) 49-58.
[7] P. Mihók, G. Semanišin, Reducible Properties of Graphs, Discuss. Math. Graph Theory 15 (1995) 11-18, doi: 10.7151/dmgt.1002.
[8] P. Mihók, G. Semanišin and R. Vasky, Additive and Hereditary Properties of Graphs are Uniquely Factorizable into Irreducible Factors, J. Graph Theory 33 (2000) 44-53, doi: 10.1002/(SICI)1097-0118(200001)33:1<44::AID-JGT5>3.0.CO;2-O.

Received 2 February 1999
Revised 8 September 1999