Factorizations of properties of graphs
Izak Broere ; Samuel John Teboho Moagi ; Peter Mihók ; Roman Vasky
Discussiones Mathematicae Graph Theory, Tome 19 (1999), p. 167-174 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

A property of graphs is any isomorphism closed class of simple graphs. For given properties of graphs ₁,₂,...,ₙ a vertex (₁, ₂, ...,ₙ)-partition of a graph G is a partition V₁,V₂,...,Vₙ of V(G) such that for each i = 1,2,...,n the induced subgraph G[Vi] has property i. The class of all graphs having a vertex (₁, ₂, ...,ₙ)-partition is denoted by ₁∘₂∘...∘ₙ. A property is said to be reducible with respect to a lattice of properties of graphs if there are n ≥ 2 properties ₁,₂,...,ₙ ∈ such that = ₁∘₂∘...∘ₙ; otherwise is irreducible in . 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.

Publié le : 1999-01-01
EUDML-ID : urn:eudml:doc:270424 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1093,
     author = {Izak Broere and Samuel John Teboho Moagi and Peter Mih\'ok and Roman Vasky},
     title = {Factorizations of properties of graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {19},
     year = {1999},
     pages = {167-174},
     zbl = {0958.05107},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1093}
}

Izak Broere; Samuel John Teboho Moagi; Peter Mihók; Roman Vasky. Factorizations of properties of graphs. Discussiones Mathematicae Graph Theory, Tome 19 (1999) pp. 167-174. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1093/

[000] [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. | Zbl 0902.05026

[001] [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.

[002] [3] A. Haviar and R. Nedela, On varieties of graphs, Discuss. Math. Graph Theory 18 (1998) 209-223, doi: 10.7151/dmgt.1077. | Zbl 0926.05033

[003] [4] R.L. Graham, M. Grötschel and L. Lovász, Handbook of combinatorics (Elsevier Science B.V., Amsterdam, 1995). | Zbl 0833.05001

[004] [5] T.R. Jensen and B. Toft, Graph colouring problems (Wiley-Interscience Publications, New York, 1995). | Zbl 0971.05046

[005] [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. | Zbl 0623.05043

[006] [7] P. Mihók, G. Semanišin, Reducible Properties of Graphs, Discuss. Math. Graph Theory 15 (1995) 11-18, doi: 10.7151/dmgt.1002. | Zbl 0829.05057

[007] [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 | Zbl 0942.05056