# Unique factorisation of additive induced-hereditary properties

• Volume: 24, Issue: 2, page 319-343
• ISSN: 2083-5892

top

## Abstract

top
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\left[{V}_{i}\right]$ 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.

## How to cite

top

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 -

## References

top
1. [1] I. Broere and J. Bucko, Divisibility in additive hereditary properties and uniquely partitionable graphs, Tatra Mt. Math. Publ. 18 (1999) 79-87. Zbl0951.05034
2. [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. Zbl0902.05027
3. [3] A. Farrugia, Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard, submitted. Zbl1053.05046
4. [4] A. Farrugia and R.B. Richter, Complexity, uniquely partitionable graphs and unique factorisation, in preparation. www.math.uwaterloo.ca/∼afarrugia/
5. [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/. Zbl1061.05070
6. [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. Zbl0949.05025
7. [7] P. Mihók, Unique Factorization Theorem, Discuss. Math. Graph Theory 20 (2000) 143-153, doi: 10.7151/dmgt.1114. Zbl0968.05032
8. [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:1<44::AID-JGT5>3.0.CO;2-O Zbl0942.05056
9. [9] G. Semanišin, On generating sets of hereditary properties, unpublished manuscript.
10. [10] J. Szigeti and Zs. Tuza, Generalized colorings and avoidable orientations, Discuss. Math. Graph Theory 17 (1997) 137-146, doi: 10.7151/dmgt.1047. Zbl0908.05039

top

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.