Discussiones
Mathematicae Graph Theory 20(2) (2000) 281-291
DOI: https://doi.org/10.7151/dmgt.1127
THE DECOMPOSABILITY OF ADDITIVE HEREDITARY PROPERTIES OF GRAPHS
Izak Broere and Michael J. Dorfling
Department of Mathematics
Faculty of Science, Rand Afrikaans University
P.O. Box 524, Auckland Park, 2006 South Africa
e-mail: ib@na.rau.ac.za
Abstract
An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. If P1,…,Pn are properties of graphs, then a (P1, …, Pn)-decomposition of a graph G is a partition E1, …, En of E(G) such that G[Ei], the subgraph of G induced by Ei, is in Pi, for i = 1, …, n. We define P1 ⊕…⊕Pn as the property { G ∈ ℑ: G has a (P1, …, Pn)−decomposition }. A property P is said to be decomposable if there exist non-trivial hereditary properties P1 and P2 such that P = P1⊕P2. We study the decomposability of the well-known properties of graphs ℑk, Ok, Wk, Tk, Sk, Dk and O p.
Keywords: property of graphs, additive, hereditary, decomposable property of graphs.
2000 Mathematics Subject Classification: O5C70.
References
| [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. |
| [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] | 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. |
| [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. |
| [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. |
Received 5 September 2000
Revised 13 November 2000
Close