Unique factorisation of additive induced-hereditary properties

Alastair Farrugia, and R. Bruce Richter. "Unique factorisation of additive induced-hereditary properties." Discussiones Mathematicae Graph Theory 24.2 (2004): 319-343. <http://eudml.org/doc/270750>.

@article{AlastairFarrugia2004,
abstract = {An additive hereditary graph property is a set of graphs, closed under isomorphism and under taking subgraphs and disjoint unions. Let ₁,...,ₙ be additive hereditary graph properties. A graph G has property (₁∘...∘ₙ) if there is a partition (V₁,...,Vₙ) of V(G) into n sets such that, for all i, the induced subgraph $G[V_i]$ is in $_i$. A property is reducible if there are properties , such that = ∘ ; otherwise it is irreducible. Mihók, Semanišin and Vasky [8] gave a factorisation for any additive hereditary property into a given number dc() of irreducible additive hereditary factors. Mihók [7] gave a similar factorisation for properties that are additive and induced-hereditary (closed under taking induced-subgraphs and disjoint unions). Their results left open the possiblity of different factorisations, maybe even with a different number of factors; we prove here that the given factorisations are, in fact, unique.},
author = {Alastair Farrugia, R. Bruce Richter},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {additive and hereditary graph classes; unique factorization},
language = {eng},
number = {2},
pages = {319-343},
title = {Unique factorisation of additive induced-hereditary properties},
url = {http://eudml.org/doc/270750},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Alastair Farrugia
AU - R. Bruce Richter
TI - Unique factorisation of additive induced-hereditary properties
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 2
SP - 319
EP - 343
AB - An additive hereditary graph property is a set of graphs, closed under isomorphism and under taking subgraphs and disjoint unions. Let ₁,...,ₙ be additive hereditary graph properties. A graph G has property (₁∘...∘ₙ) if there is a partition (V₁,...,Vₙ) of V(G) into n sets such that, for all i, the induced subgraph $G[V_i]$ is in $_i$. A property is reducible if there are properties , such that = ∘ ; otherwise it is irreducible. Mihók, Semanišin and Vasky [8] gave a factorisation for any additive hereditary property into a given number dc() of irreducible additive hereditary factors. Mihók [7] gave a similar factorisation for properties that are additive and induced-hereditary (closed under taking induced-subgraphs and disjoint unions). Their results left open the possiblity of different factorisations, maybe even with a different number of factors; we prove here that the given factorisations are, in fact, unique.
LA - eng
KW - additive and hereditary graph classes; unique factorization
UR - http://eudml.org/doc/270750
ER -