# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

# Discussiones Mathematicae Graph Theory

## ON THE COMPLETENESS OF DECOMPOSABLE PROPERTIES OF GRAPHS

 Mariusz Hałuszczak Institute of Mathematics Technical University of Zielona Góra Podgórna 50, 65-246 Zielona Góra, Poland e-mail: M.Hałuszczak@im.uz.zgora.pl Pavol Vateha Department of Geometry and Algebra Faculty of Science, P.J. Safárik University Jesenná 5, 041 54 Košice, Slovak Republic e-mail: vateha@duro.upjs.sk

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