Factorizations and characterizations of induced‐hereditary and compositive properties
- 25 February 2005
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 49 (1) , 11-27
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
Keywords
This publication has 14 references indexed in Scilit:
- Unique factorisation of additive induced-hereditary propertiesDiscussiones Mathematicae Graph Theory, 2004
- Meet- and join-irreducibility of additive hereditary properties of graphsDiscrete Mathematics, 2002
- Unique factorization theoremDiscussiones Mathematicae Graph Theory, 2000
- Additive and hereditary properties of graphs are uniquely factorizable into irreducible factorsJournal of Graph Theory, 1999
- Complexity of graph partition problems1999
- Generalized colorings and avoidable orientationsDiscussiones Mathematicae Graph Theory, 1997
- A survey of hereditary properties of graphsDiscussiones Mathematicae Graph Theory, 1997
- Containment Graphs, Posets, and Related Classes of GraphsAnnals of the New York Academy of Sciences, 1989
- On the structure of hereditary classes of graphsJournal of Graph Theory, 1986
- Characterizing intersection classes of graphsDiscrete Mathematics, 1985