Discussiones
Mathematicae Graph Theory 19(2) (1999) 229-236
DOI: https://doi.org/10.7151/dmgt.1097
ON THE COMPLETENESS OF DECOMPOSABLE PROPERTIES OF GRAPHS
Mariusz Hałuszczak Institute of Mathematics |
Pavol Vateha Department of Geometry and Algebra |
Abstract
Let P1, P2 be additive hereditary properties of graphs. A (P1, P2)-decomposition of a graph G is a partition of E(G) into sets E1, E2 such that induced subgraph G[Ei] has the property Pi, i = 1,2. Let us define a property P1⊕P2 by {G: G has a (P1,P2)-decomposition}.
A property D is said to be decomposable if there exists nontrivial additive hereditary properties P1, P2 such that D = P1⊕P2. In this paper we determine the completeness of some decomposable properties and we characterize the decomposable properties of completeness 2.
Keywords: decomposition, hereditary property, completeness.
1991 Mathematics Subject Classification: 05C55, 05C70.
References
[1] | L.W. Beineke, Decompositions of complete graphs into forests, Magyar Tud. Akad. Mat. Kutato Int. Kozl. 9 (1964) 589-594. |
[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. |
[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 |
[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. |
[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. |
Received 12 February 1999
Revised 20 October 1999
Close