Unique factorization theorem

Peter Mihók

Discussiones Mathematicae Graph Theory (2000)

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

Abstract

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

How to cite

top

Peter 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. [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. [2] A. Berger, Reducible properties have infinitely many minimal forbidden subgraphs, manuscript. 
  3. [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. [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. [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. [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. [7] R.L. Graham, M. Grötschel and L. Lovász, Handbook of combinatorics (Elsevier Science B.V., Amsterdam, 1995). Zbl0833.05001
  8. [8] T.R. Jensen and B. Toft, Graph colouring problems (Wiley-Interscience Publications, New York, 1995). Zbl0971.05046
  9. [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. [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. [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. [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. [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. [14] G. Semanišin, On generating sets of induced-hereditary properties, manuscript. Zbl1018.05089

Citations in EuDML Documents

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

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.