Geodesic
Unique factorization theorem
Discussiones Mathematicae. Graph Theory, Tome 20 (2000) no. 1, pp. 143-154

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

A property of graphs is any class of graphs closed under isomorphism. A property of graphs is induced-hereditary and additive if it is closed under taking induced subgraphs and disjoint unions of graphs, respectively. Let ₁,₂, ...,ₙ be properties of graphs. A graph G is (₁,₂,...,ₙ)-partitionable (G has property ₁ º₂ º... ºₙ) if the vertex set V(G) of G can be partitioned into n sets V₁,V₂,..., Vₙ such that the subgraph G[V_i] of G induced by V_i belongs to _i; i = 1,2,...,n. A property is said to be reducible if there exist properties ₁ and ₂ such that = ₁ º₂; otherwise the property is irreducible. We prove that every additive and induced-hereditary property is uniquely factorizable into irreducible factors. Moreover the unique factorization implies the existence of uniquely (₁,₂, ...,ₙ)-partitionable graphs for any irreducible properties ₁,₂, ...,ₙ.
Keywords: induced-hereditary, additive property of graphs, reducible property of graphs, unique factorization, uniquely partitionable graphs, generating sets 
Mihók, Peter. Unique factorization theorem. Discussiones Mathematicae. Graph Theory, Tome 20 (2000) no. 1, pp. 143-154. http://geodesic.mathdoc.fr/item/DMGT_2000_20_1_a11/
@article{DMGT_2000_20_1_a11,
     author = {Mih\'ok, Peter},
     title = {Unique factorization theorem},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {143--154},
     year = {2000},
     volume = {20},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2000_20_1_a11/}
}
TY  - JOUR
AU  - Mihók, Peter
TI  - Unique factorization theorem
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2000
SP  - 143
EP  - 154
VL  - 20
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2000_20_1_a11/
LA  - en
ID  - DMGT_2000_20_1_a11
ER  - 
%0 Journal Article
%A Mihók, Peter
%T Unique factorization theorem
%J Discussiones Mathematicae. Graph Theory
%D 2000
%P 143-154
%V 20
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2000_20_1_a11/
%G en
%F DMGT_2000_20_1_a11

[1] D. Achlioptas, J.I. Brown, D.G. Corneil and M.S.O. Molloy, The existence of uniquely -G colourable graphs, Discrete Math. 179 (1998) 1-11, doi: 10.1016/S0012-365X(97)00022-8.

[2] A. Berger, Reducible properties have infinitely many minimal forbidden subgraphs, manuscript.

[3] B. Bollobás and A.G. Thomason, Hereditary and monotone properties of graphs, in: R.L. Graham and J. Nesetril, eds., The mathematics of Paul Erdős, II, Algorithms and Combinatorics vol. 14 (Springer-Verlag, 1997), 70-78.

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

[5] I. Broere, J. Bucko, Divisibility in additive hereditary graph properties and uniquely partitionable graphs, Tatra Mountains Math. Publications 18 (1999) 79-87.

[6] E.J. Cockayne, Color clasess for r-graphs, Canad. Math. Bull. 15 (3) (1972) 349-354, doi: 10.4153/CMB-1972-063-2.

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

[8] T.R. Jensen and B. Toft, Graph colouring problems (Wiley-Interscience Publications, New York, 1995).

[9] J. Kratochvíl, P. Mihók, Hom-properties are uniquely factorizable into irreducible factors, Discrete Math. 213 (2000) 189-194, doi: 10.1016/S0012-365X(99)00179-X.

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

[11] P. Mihók and R. Vasky, On the factorization of reducible properties of graphs into irreducible factors, Discuss. Math. Graph Theory 15 (1995) 195-203, doi: 10.7151/dmgt.1017.

[12] P. Mihók, Reducible properties and uniquely partitionable graphs, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 49 (1999) 213-218.

[13] 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

[14] G. Semanišin, On generating sets of induced-hereditary properties, manuscript.