Geodesic
On some variations of extremal graph problems
Discussiones Mathematicae. Graph Theory, Tome 17 (1997) no. 1, pp. 67-76

Voir la notice de l'article provenant de la source Library of Science

A set P of graphs is termed hereditary property if and only if it contains all subgraphs of any graph G belonging to P. A graph is said to be maximal with respect to a hereditary property P (shortly P-maximal) whenever it belongs to P and none of its proper supergraphs of the same order has the property P. A graph is P-extremal if it has a the maximum number of edges among all P-maximal graphs of given order. The number of its edges is denoted by ex(n, P). If the number of edges of a P-maximal graph is minimum, then the graph is called P-saturated and its number of edges is denoted by sat(n, P).
Keywords: hereditary properties of graphs, maximal graphs, extremal graphs, saturated graphs 
Semanišin, Gabriel. On some variations of extremal graph problems. Discussiones Mathematicae. Graph Theory, Tome 17 (1997) no. 1, pp. 67-76. http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a2/
@article{DMGT_1997_17_1_a2,
     author = {Semani\v{s}in, Gabriel},
     title = {On some variations of extremal graph problems},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {67--76},
     year = {1997},
     volume = {17},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a2/}
}
TY  - JOUR
AU  - Semanišin, Gabriel
TI  - On some variations of extremal graph problems
JO  - Discussiones Mathematicae. Graph Theory
PY  - 1997
SP  - 67
EP  - 76
VL  - 17
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a2/
LA  - en
ID  - DMGT_1997_17_1_a2
ER  - 
%0 Journal Article
%A Semanišin, Gabriel
%T On some variations of extremal graph problems
%J Discussiones Mathematicae. Graph Theory
%D 1997
%P 67-76
%V 17
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a2/
%G en
%F DMGT_1997_17_1_a2

[1] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishwa Intern. Publication, Gulbarga, 1991) 41-68.

[2] P. Erdős, Some recent results on extremal problems in graph theory, Results in: P. Rosentstiehl, ed., Theory of Graphs (Gordon and Breach New York; Dunod Paris, 1967) 117-123; MR37#2634.

[3] P. Erdős, On some new inequalities concerning extremal properties of graphs, in: P. Erdős and G. Katona, eds., Theory of Graphs (Academic Press, New York, 1968) 77-81; MR38#1026.

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

[5] R. Lick and A. T. White, k-degenerate graphs, Canadian J. Math. 22 (1970) 1082-1096; MR42#1715.

[6] P. Mihók, On graphs critical with respect to vertex partition numbers, Discrete Math. 37 (1981) 123-126, doi: 10.1016/0012-365X(81)90146-1.

[7] P. Mihók and G. Semanišin, On the chromatic number of reducible hereditary properties (submitted).

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

[9] M. Simonovits, A method for solving extremal problems in graph theory, stability problems, in: P. Erdős and G. Katona, eds., Theory of Graphs (Academic Press, New York, 1968) 279-319; MR 38#2056.

[10] M. Simonovits, Extremal graph problems with symmetrical extremal graphs. Additional chromatical conditions, Discrete Math. 7 (1974) 349-376; MR49#2459.

[11] M. Simonovits, Extremal graph theory, in: L.W. Beineke and R.J. Wilson, eds., Selected Topics in Graph Theory vol. 2 (Academic Press, London, 1983) 161-200.

[12] P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436-452 (Hungarian); MR8,284j.

[13] P. Turán, On the theory of graph, Colloquium Math. 3 (1954) 19-30; MR15,476b.

[14] L. Kászonyi and Z. Tuza, Saturated graphs with minimal number of edges, J. Graph Theory 10 (1986) 203-210, doi: 10.1002/jgt.3190100209.