# On the completeness of decomposable properties of graphs

Mariusz Hałuszczak; Pavol Vateha

Discussiones Mathematicae Graph Theory (1999)

- Volume: 19, Issue: 2, page 229-236
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMariusz Hałuszczak, and Pavol Vateha. "On the completeness of decomposable properties of graphs." Discussiones Mathematicae Graph Theory 19.2 (1999): 229-236. <http://eudml.org/doc/270259>.

@article{MariuszHałuszczak1999,

abstract = {Let ₁,₂ be additive hereditary properties of graphs. A (₁,₂)-decomposition of a graph G is a partition of E(G) into sets E₁, E₂ such that induced subgraph $G[E_i]$ has the property $_i$, i = 1,2. Let us define a property ₁⊕₂ by G: G has a (₁,₂)-decomposition.
A property D is said to be decomposable if there exists nontrivial additive hereditary properties ₁, ₂ such that D = ₁⊕₂. In this paper we determine the completeness of some decomposable properties and we characterize the decomposable properties of completeness 2.},

author = {Mariusz Hałuszczak, Pavol Vateha},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {decomposition; hereditary property; completeness; hereditary properties; partition},

language = {eng},

number = {2},

pages = {229-236},

title = {On the completeness of decomposable properties of graphs},

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

volume = {19},

year = {1999},

}

TY - JOUR

AU - Mariusz Hałuszczak

AU - Pavol Vateha

TI - On the completeness of decomposable properties of graphs

JO - Discussiones Mathematicae Graph Theory

PY - 1999

VL - 19

IS - 2

SP - 229

EP - 236

AB - Let ₁,₂ be additive hereditary properties of graphs. A (₁,₂)-decomposition of a graph G is a partition of E(G) into sets E₁, E₂ such that induced subgraph $G[E_i]$ has the property $_i$, i = 1,2. Let us define a property ₁⊕₂ by G: G has a (₁,₂)-decomposition.
A property D is said to be decomposable if there exists nontrivial additive hereditary properties ₁, ₂ such that D = ₁⊕₂. In this paper we determine the completeness of some decomposable properties and we characterize the decomposable properties of completeness 2.

LA - eng

KW - decomposition; hereditary property; completeness; hereditary properties; partition

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

ER -

## References

top- [1] L.W. Beineke, Decompositions of complete graphs into forests, Magyar Tud. Akad. Mat. Kutato Int. Kozl. 9 (1964) 589-594. Zbl0137.18104
- [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] M. Borowiecki and M. Hałuszczak, Decomposition of some classes of graphs, (manuscript).
- [4] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishwa International Publication, Gulbarga, 1991) 41-68.
- [5] S.A. Burr, J.A. Roberts, On Ramsey numbers for stars, Utilitas Math. 4 (1973) 217-220 Zbl0293.05119
- [6] G. Chartrand and L. Lesnak, Graphs and Digraphs (Wadsworth & Brooks/Cole, Monterey, California, 1986).
- [7] E.J. Cockayne, Colour classes for r-graphs, Canad. Math. Bull. 15 (1972) 349-354, doi: 10.4153/CMB-1972-063-2. Zbl0254.05106
- [8] P. Mihók Additive hereditary properties and uniquely partitionable graphs, in: M. Borowiecki, Z. Skupień, eds., Graphs, Hypergraphs and Matroids (Zielona Góra, 1985) 49-58.
- [9] P. Mihók and G. Semanišin, Generalized Ramsey Theory and Decomposable Properties of Graphs, (manuscript).
- [10] L. Volkmann, Fundamente der Graphentheorie (Springer, Wien, New York, 1996), doi: 10.1007/978-3-7091-9449-2.

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