Geodesic
Unique factorisation of additive induced-hereditary properties
Discussiones Mathematicae. Graph Theory, Tome 24 (2004) no. 2, pp. 319-343.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: additive and hereditary graph classes, unique factorization 
@article{DMGT_2004_24_2_a12,
     author = {Farrugia, Alastair and Richter, R.},
     title = {Unique factorisation of additive induced-hereditary properties},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {319--343},
     publisher = {mathdoc},
     volume = {24},
     number = {2},
     year = {2004},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2004_24_2_a12/}
}
TY  - JOUR
AU  - Farrugia, Alastair
AU  - Richter, R.
TI  - Unique factorisation of additive induced-hereditary properties
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2004
SP  - 319
EP  - 343
VL  - 24
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2004_24_2_a12/
LA  - en
ID  - DMGT_2004_24_2_a12
ER  - 
%0 Journal Article
%A Farrugia, Alastair
%A Richter, R.
%T Unique factorisation of additive induced-hereditary properties
%J Discussiones Mathematicae. Graph Theory
%D 2004
%P 319-343
%V 24
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2004_24_2_a12/
%G en
%F DMGT_2004_24_2_a12
Farrugia, Alastair; Richter, R. Unique factorisation of additive induced-hereditary properties. Discussiones Mathematicae. Graph Theory, Tome 24 (2004) no. 2, pp. 319-343. http://geodesic.mathdoc.fr/item/DMGT_2004_24_2_a12/

[1] I. Broere and J. Bucko, Divisibility in additive hereditary properties and uniquely partitionable graphs, Tatra Mt. Math. Publ. 18 (1999) 79-87.

[2] I. Broere, M. Frick and G. Semanišin, Maximal graphs with respect to hereditary properties, Discuss. Math. Graph Theory 17 (1997) 51-66, doi: 10.7151/dmgt.1038.

[3] A. Farrugia, Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard, submitted.

[4] A. Farrugia and R.B. Richter, Complexity, uniquely partitionable graphs and unique factorisation, in preparation. www.math.uwaterloo.ca/∼afarrugia/

[5] A. Farrugia and R.B. Richter, Unique factorisation of induced-hereditary disjoint compositive properties, Research Report CORR 2002-ZZ (2002) Department of Combinatorics and Optimization, University of Waterloo. www.math.uwaterloo.ca/~afarrugia/.

[6] J. Kratochvil and P. Mihók, Hom-properties are uniquely factorizable into irreducible factors, Discrete Math. 213 (2000) 189-194, doi: 10.1016/S0012-365X(99)00179-X.

[7] P. Mihók, Unique Factorization Theorem, Discuss. Math. Graph Theory 20 (2000) 143-153, doi: 10.7151/dmgt.1114.

[8] P. Mihók, G. Semanišin and R. Vasky, Additive and hereditary properties of graphs are uniquely factorizable into irreducible factors, J. Graph Theory 33 (2000) 44-53, doi: 10.1002/(SICI)1097-0118(200001)33:144::AID-JGT5>3.0.CO;2-O

[9] G. Semanišin, On generating sets of hereditary properties, unpublished manuscript.

[10] J. Szigeti and Zs. Tuza, Generalized colorings and avoidable orientations, Discuss. Math. Graph Theory 17 (1997) 137-146, doi: 10.7151/dmgt.1047.