Geodesic
Factorizations of properties of graphs
Discussiones Mathematicae. Graph Theory, Tome 19 (1999) no. 2, pp. 167-174.

Voir la notice de l'article provenant de la source Library of Science

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[V_i] 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.
Keywords: factorization, property of graphs, irreducible property, reducible property, lattice of properties of graphs 
@article{DMGT_1999_19_2_a4,
     author = {Broere, Izak and Teboho Moagi, Samuel and Mih\'ok, Peter and Vasky, Roman},
     title = {Factorizations of properties of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {167--174},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {1999},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_1999_19_2_a4/}
}
TY  - JOUR
AU  - Broere, Izak
AU  - Teboho Moagi, Samuel
AU  - Mihók, Peter
AU  - Vasky, Roman
TI  - Factorizations of properties of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 1999
SP  - 167
EP  - 174
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_1999_19_2_a4/
LA  - en
ID  - DMGT_1999_19_2_a4
ER  - 
%0 Journal Article
%A Broere, Izak
%A Teboho Moagi, Samuel
%A Mihók, Peter
%A Vasky, Roman
%T Factorizations of properties of graphs
%J Discussiones Mathematicae. Graph Theory
%D 1999
%P 167-174
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_1999_19_2_a4/
%G en
%F DMGT_1999_19_2_a4
Broere, Izak; Teboho Moagi, Samuel; Mihók, Peter; Vasky, Roman. Factorizations of properties of graphs. Discussiones Mathematicae. Graph Theory, Tome 19 (1999) no. 2, pp. 167-174. http://geodesic.mathdoc.fr/item/DMGT_1999_19_2_a4/

[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:144::AID-JGT5>3.0.CO;2-O