DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 20(1) (2000) 143-154
DOI: https://doi.org/10.7151/dmgt.1114

Unique Factorization Theorem

Peter Mihók

Mathematical Institute of Slovak Academy of Sciences
Grešákova 6, 040 01 Košice, Slovakia
and
Faculty of Economics, Technical University
B. Nšemcovej 32, 040 01 Košice, Slovakia
e-mail: mihok@saske.sk

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 P1,P2, …,Pn be properties of graphs. A graph G is (P1,P2,...,Pn)-partitionable (G has property P1 ºP2 º… ºPn) if the vertex set V(G) of G can be partitioned into n sets V1,V2,..., Vn such that the subgraph G[Vi] of G induced by Vi belongs to Pi; i = 1,2,...,n. A property ℜ is said to be reducible if there exist properties P1 and P2 such that ℜ = P1 ºP2; 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 (P1,P2, ...,Pn)-partitionable graphs for any irreducible properties P1,P2, ...,Pn.

Keywords: induced-hereditary, additive property of graphs, reducible property of graphs, unique factorization, uniquely partitionable graphs, generating sets

References

[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:1<44::AID-JGT5>3.0.CO;2-O.
[14] G. Semanišin, On generating sets of induced-hereditary properties, manuscript.

Received 22 March 2000
Revised 4 May 2000

Close