Factorizations and characterizations of induced-hereditary and compositive properties

✍ Scribed by Alastair Farrugia; Peter Mihók; R. Bruce Richter; Gabriel Semanivšin

• Publisher: John Wiley and Sons
• Year: 2005
• Tongue: English
• Weight: 154 KB
• Volume: 49
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20062

✦ Synopsis

Abstract

An Erratum has been published for this article in Journal of Graph Theory 50:261, 2005.

A graph property (i.e., a set of graphs) is hereditary (respectively, induced‐hereditary) if it is closed under taking subgraphs (resp., induced‐subgraphs), while the property is additive if it is closed under disjoint unions. If ${\cal P}$ and ${\cal Q}$ are properties, the product ${\cal P}\circ {\cal Q}$ consists of all graphs G for which there is a partition of the vertex set of G into (possibly empty) subsets A and B with G[A] $\in {\cal P}$ and G[B] $\in {\cal Q}$. A property is reducible if it is the product of two other properties, and irreducible otherwise.

We show that very few reducible induced‐hereditary properties have a unique factorization into irreducibles, and we describe them completely. On the other hand, we give a new and simpler proof that additive hereditary properties have a unique factorization into irreducible additive hereditary properties [J. Graph Theory 33 (2000), 44–53]. We also introduce analogs of additive induced‐hereditary properties, and characterize them in the style of Scheinerman [Discrete Math. 55 (1985), 185–193]. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 11–27, 2005