Additive and hereditary properties of graphs are uniquely factorizable into irreducible factors
✍ Scribed by Mih�k, Peter; Semani?in, Gabriel; Vasky, Roman
- Publisher
- John Wiley and Sons
- Year
- 2000
- Tongue
- English
- Weight
- 210 KB
- Volume
- 33
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
A hereditary property of graphs is any class of graphs closed under isomorphism and subgraphs. Let P 1 , P 2 , . . . , P n be hereditary properties of graphs. We say that a graph G has property P 1
. . , V n such that the subgraph of G induced by V i belongs to P i ; i = 1, 2, . . . , n. A hereditary property is said to be reducible if there exist hereditary properties P 1 and P 2 such that R = P 1 • P 2 ; otherwise it is irreducible. We prove that the factorization of a reducible hereditary property into irreducible factors is unique whenever the property is additive, i.e., it is closed under the disjoint union of graphs.