On the completeness of decomposable properties of graphs
Mariusz Hałuszczak ; Pavol Vateha
Discussiones Mathematicae Graph Theory, Tome 19 (1999), p. 229-236 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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[Ei] 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.

Publié le : 1999-01-01
EUDML-ID : urn:eudml:doc:270259 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1097,
     author = {Mariusz Ha\l uszczak and Pavol Vateha},
     title = {On the completeness of decomposable properties of graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {19},
     year = {1999},
     pages = {229-236},
     zbl = {0958.05112},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1097}
}

Mariusz Hałuszczak; Pavol Vateha. On the completeness of decomposable properties of graphs. Discussiones Mathematicae Graph Theory, Tome 19 (1999) pp. 229-236. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1097/

[000] [1] L.W. Beineke, Decompositions of complete graphs into forests, Magyar Tud. Akad. Mat. Kutato Int. Kozl. 9 (1964) 589-594. | Zbl 0137.18104

[001] [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. | Zbl 0902.05026

[002] [3] M. Borowiecki and M. Hałuszczak, Decomposition of some classes of graphs, (manuscript).

[003] [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.

[004] [5] S.A. Burr, J.A. Roberts, On Ramsey numbers for stars, Utilitas Math. 4 (1973) 217-220 | Zbl 0293.05119

[005] [6] G. Chartrand and L. Lesnak, Graphs and Digraphs (Wadsworth & Brooks/Cole, Monterey, California, 1986).

[006] [7] E.J. Cockayne, Colour classes for r-graphs, Canad. Math. Bull. 15 (1972) 349-354, doi: 10.4153/CMB-1972-063-2. | Zbl 0254.05106

[007] [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.

[008] [9] P. Mihók and G. Semanišin, Generalized Ramsey Theory and Decomposable Properties of Graphs, (manuscript).

[009] [10] L. Volkmann, Fundamente der Graphentheorie (Springer, Wien, New York, 1996), doi: 10.1007/978-3-7091-9449-2.