# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

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

# Discussiones Mathematicae Graph Theory

## MAXIMAL GRAPHS WITH RESPECT TO HEREDITARY PROPERTIES

 Izak Broere Department of Mathematics Rand Afrikaans University P.O. Box 524, Auckland Park, 2006 South Africa Marietjie Frick Department of Mathematics, Applied Mathematics and Astronomy University of South Africa P.O. Box 392, Pretoria, 0001 South Africa Gabriel Semanišin Department of Geometry and Algebra P.J.Šafárik University 041 54 Košice, Slovak Republic

## Abstract

A property of graphs is a non-empty set of graphs. A property P is called hereditary if every subgraph of any graph with property P also has property P. Let P1, …,Pn be properties of graphs. We say that a graph G has property P1 º…ºPn if the vertex set of G can be partitioned into n sets V1, …,Vn such that the subgraph of G induced by Vi has property Pi; i = 1,…, n. A hereditary property R is said to be reducible if there exist two hereditary properties P1 and P2 such that R=P1ºP2. If P is a hereditary property, then a graph G is called P- maximal if G has property P but G+e does not have property P for every e ∈ E([`G]). We present some general results on maximal graphs and also investigate P-maximal graphs for various specific choices of P, including reducible hereditary properties.

Keywords: hereditary property of graphs, maximal graphs, vertex partition.

1991 Mathematics Subject Classification: 05C15, O5C75.

## References

 [1] G. Benadé, I. Broere, B. Jonck and M. Frick, Uniquely (m,k)τ-colourable graphs and k-τ-saturated graphs, Discrete Math. 162 (1996) 13-22, doi: 10.1016/0012-365X(95)00301-C. [2] M. Borowiecki, I. Broere and P. Mihók, Minimal reducible bounds for planar graphs, submitted. [3] M. Borowiecki, J. Ivančo, P. Mihók and G. Semanišin, Sequences realizable by maximal k-degenerate graphs, J. Graph Theory 19 (1995) 117-124; MR96e:05078. [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] I. Broere, M. Frick and P. Mihók, On the order of uniquely partitionable graphs, submitted. [6] G. Chartrand and L. Lesniak, Graphs and Digraphs, (Wadsworth & Brooks/Cole, Monterey California, 1986). [7] P. Erdős and T. Gallai, On the minimal number of vertices representing the edges of a graph, Magyar Tud. Akad. Math. Kutató Int. Közl. 6 (1961) 181-203; MR 26#1878. [8] Z. Filáková, P. Mihók and G. Semanišin, On maximal k-degenerate graphs, to appear in Math. Slovaca. [9] A. Hajnal, A theorem on k-saturated graphs, Canad. J. Math. 17 (1965) 720-724; MR31#3354. [10] L. Kászonyi and Zs. Tuza, Saturated graphs with minimal number of edges, J. Graph Theory 10 (1986) 203-210, doi: 10.1002/jgt.3190100209. [11] J. Kratochvíl, P. Mihók and G. Semanišin, Graphs maximal with respect to hom-properties, Discussiones Mathematicae Graph Theory 17 (1997) 77-88, doi: 10.7151/dmgt.1040. [12] R. Lick and A.T. White, k-degenerate graphs, Canad. J. Math. 22 (1970) 1082-1096; MR42#1715. [13] P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: M. Borowiecki and Z. Skupień, eds., Graphs, Hypergraphs and Matroids (Zielona Góra, 1985) 49-58. [14] P. Mihók and G. Semanišin, Reducible properties of graphs, Discussiones Math. Graph Theory 15 (1995) 11-18; MR96c:05149, doi: 10.7151/dmgt.1002. [15] J. Mitchem, An extension of Brooks' theorem to r-degenerate graphs, Discrete Math. 17 (1977) 291-298; MR 55#12561. [16] J. Mitchem, Maximal k-degenerate graphs, Utilitas Math. 11 (1977) 101-106. [17] G. Semanišin, On some variations of extremal graph problems, Discussiones Mathematicae Graph Theory 17 (1997) 67-76, doi: 10.7151/dmgt.1039. [18] J.M.S. Simoes-Pereira, On graphs uniquely partitionable into n-degenerate subgraphs, in: Infinite and finite sets - Colloquia Math. Soc. J. Bólyai 10 (North-Holland Amsterdam, 1975) 1351-1364; MR53#2758. [19] J.M.S. Simoes-Pereira, A survey on k-degenerate graphs, Graph Theory Newsletter 5 (6) (75/76) 1-7; MR 55#199.