# The decomposability of additive hereditary properties of graphs

Izak Broere; Michael J. Dorfling

Discussiones Mathematicae Graph Theory (2000)

- Volume: 20, Issue: 2, page 281-291
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topIzak Broere, and Michael J. Dorfling. "The decomposability of additive hereditary properties of graphs." Discussiones Mathematicae Graph Theory 20.2 (2000): 281-291. <http://eudml.org/doc/270686>.

@article{IzakBroere2000,

abstract = {An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. If ₁,...,ₙ are properties of graphs, then a (₁,...,ₙ)-decomposition of a graph G is a partition E₁,...,Eₙ of E(G) such that $G[E_i]$, the subgraph of G induced by $E_i$, is in $_i$, for i = 1,...,n. We define ₁ ⊕...⊕ ₙ as the property G ∈ : G has a (₁,...,ₙ)-decomposition. A property is said to be decomposable if there exist non-trivial hereditary properties ₁ and ₂ such that = ₁⊕ ₂. We study the decomposability of the well-known properties of graphs ₖ, ₖ, ₖ, ₖ, ₖ, ₖ and $ ^\{p\}$.},

author = {Izak Broere, Michael J. Dorfling},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {property of graphs; additive; hereditary; decomposable property of graphs; additive hereditary property; decomposability},

language = {eng},

number = {2},

pages = {281-291},

title = {The decomposability of additive hereditary properties of graphs},

url = {http://eudml.org/doc/270686},

volume = {20},

year = {2000},

}

TY - JOUR

AU - Izak Broere

AU - Michael J. Dorfling

TI - The decomposability of additive hereditary properties of graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2000

VL - 20

IS - 2

SP - 281

EP - 291

AB - An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. If ₁,...,ₙ are properties of graphs, then a (₁,...,ₙ)-decomposition of a graph G is a partition E₁,...,Eₙ of E(G) such that $G[E_i]$, the subgraph of G induced by $E_i$, is in $_i$, for i = 1,...,n. We define ₁ ⊕...⊕ ₙ as the property G ∈ : G has a (₁,...,ₙ)-decomposition. A property is said to be decomposable if there exist non-trivial hereditary properties ₁ and ₂ such that = ₁⊕ ₂. We study the decomposability of the well-known properties of graphs ₖ, ₖ, ₖ, ₖ, ₖ, ₖ and $ ^{p}$.

LA - eng

KW - property of graphs; additive; hereditary; decomposable property of graphs; additive hereditary property; decomposability

UR - http://eudml.org/doc/270686

ER -

## References

top- [1] M. Borowiecki and M. Hałuszczak, Decompositions of some classes of graphs, Report No. IM-3-99, Institute of Mathematics, Technical University of Zielona Góra, 1999. Zbl0905.05061
- [2] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. Zbl0902.05026
- [3] S.A. Burr, M.S. Jacobson, P. Mihók and G. Semanišin, Generalized Ramsey theory and decomposable properties of graphs, Discuss. Math. Graph Theory 19 (1999) 199-217, doi: 10.7151/dmgt.1095. Zbl0958.05094
- [4] M. Hałuszczak and P. Vateha, On the completeness of decomposable properties of graphs, Discuss. Math. Graph Theory 19 (1999) 229-236, doi: 10.7151/dmgt.1097.
- [5] 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
- [6] J. Nesetril and V. Rödl, Simple proof of the existence of restricted Ramsey graphs by means of a partite construction, Combinatorica 1 (1981) 199-202, doi: 10.1007/BF02579274. Zbl0491.05044

## 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.