PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2000 | 20 | 1 | 143-154
Tytuł artykułu

Unique factorization theorem

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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 𝓟₁,𝓟₂, ...,𝓟ₙ.
Wydawca
Rocznik
Tom
20
Numer
1
Strony
143-154
Opis fizyczny
Daty
wydano
2000
otrzymano
2000-03-22
poprawiono
2000-05-04
Twórcy
autor
  • Mathematical Institute of Slovak Academy of Sciences, Grešákova 6, 040 01 Košice, Slovakia
  • Faculty of Economics, Technical University Košice, Slovakia
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1114
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.