# Unique factorisation of additive induced-hereditary properties

Alastair Farrugia; R. Bruce Richter

Discussiones Mathematicae Graph Theory (2004)

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

## Access Full Article

top## Abstract

top## How to cite

topAlastair 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] 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] 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] A. Farrugia, Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard, submitted. Zbl1053.05046
- [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/. Zbl1061.05070
- [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] P. Mihók, Unique Factorization Theorem, Discuss. Math. Graph Theory 20 (2000) 143-153, doi: 10.7151/dmgt.1114. Zbl0968.05032
- [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] 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. Zbl0908.05039

## Citations in EuDML Documents

top## NotesEmbed ?

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