# Unique factorization theorem

Discussiones Mathematicae Graph Theory (2000)

- Volume: 20, Issue: 1, page 143-154
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topPeter Mihók. "Unique factorization theorem." Discussiones Mathematicae Graph Theory 20.1 (2000): 143-154. <http://eudml.org/doc/270654>.

@article{PeterMihók2000,

abstract = {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 Vi 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 ₁,₂, ...,ₙ.},

author = {Peter Mihók},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {induced-hereditary; additive property of graphs; reducible property of graphs; unique factorization; uniquely partitionable graphs; generating sets; additive property; reducible property; partitionable graphs; partition; induced-hereditary property; factors},

language = {eng},

number = {1},

pages = {143-154},

title = {Unique factorization theorem},

url = {http://eudml.org/doc/270654},

volume = {20},

year = {2000},

}

TY - JOUR

AU - Peter Mihók

TI - Unique factorization theorem

JO - Discussiones Mathematicae Graph Theory

PY - 2000

VL - 20

IS - 1

SP - 143

EP - 154

AB - 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 Vi 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 ₁,₂, ...,ₙ.

LA - eng

KW - induced-hereditary; additive property of graphs; reducible property of graphs; unique factorization; uniquely partitionable graphs; generating sets; additive property; reducible property; partitionable graphs; partition; induced-hereditary property; factors

UR - http://eudml.org/doc/270654

ER -

## References

top- [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. Zbl0885.05062
- [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. Zbl0866.05030
- [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. Zbl0902.05026
- [5] I. Broere, J. Bucko, Divisibility in additive hereditary graph properties and uniquely partitionable graphs, Tatra Mountains Math. Publications 18 (1999) 79-87. Zbl0951.05034
- [6] E.J. Cockayne, Color clasess for r-graphs, Canad. Math. Bull. 15 (3) (1972) 349-354, doi: 10.4153/CMB-1972-063-2. Zbl0254.05106
- [7] R.L. Graham, M. Grötschel and L. Lovász, Handbook of combinatorics (Elsevier Science B.V., Amsterdam, 1995). Zbl0833.05001
- [8] T.R. Jensen and B. Toft, Graph colouring problems (Wiley-Interscience Publications, New York, 1995). Zbl0971.05046
- [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. Zbl0949.05025
- [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. Zbl0623.05043
- [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. Zbl0845.05076
- [12] P. Mihók, Reducible properties and uniquely partitionable graphs, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 49 (1999) 213-218. Zbl0937.05042
- [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:1<44::AID-JGT5>3.0.CO;2-O Zbl0942.05056
- [14] G. Semanišin, On generating sets of induced-hereditary properties, manuscript. Zbl1018.05089

## Citations in EuDML Documents

top- Gabriel Semanišin, On generating sets of induced-hereditary properties
- Alastair Farrugia, R. Bruce Richter, Unique factorisation of additive induced-hereditary properties
- Jozef Bucko, Peter Mihók, On infinite uniquely partitionable graphs and graph properties of finite character
- Izak Broere, Jozef Bucko, Peter Mihók, Criteria for of the existence of uniquely partitionable graphs with respect to additive induced-hereditary properties
- Jozef Bucko, Peter Mihók, On uniquely partitionable relational structures and object systems
- Peter Mihók, Gabriel Semanišin, Unique factorization theorem for object-systems