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 19(2) (1999) 167-174
DOI: 10.7151/dmgt.1093

FACTORIZATIONS OF PROPERTIES OF GRAPHS

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
e-mail: ib@na.rau.ac.za

Peter Mihók

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

Roman Vasky

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

e-mail: vasky@rsl.sk

Abstract

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.

References

[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