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
@article{DMGT_2000_20_1_a11,
author = {Mih\'ok, Peter},
title = {Unique factorization theorem},
journal = {Discussiones Mathematicae. Graph Theory},
pages = {143--154},
publisher = {mathdoc},
volume = {20},
number = {1},
year = {2000},
language = {en},
url = {http://geodesic.mathdoc.fr/item/DMGT_2000_20_1_a11/}
}
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/