Geodesic
Maximal graphs with respect to hereditary properties
Discussiones Mathematicae. Graph Theory, Tome 17 (1997) no. 1, pp. 51-66

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

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 P₁, ...,Pₙ be properties of graphs. We say that a graph G has property P₁∘...∘Pₙ if the vertex set of G can be partitioned into n sets V₁, ...,Vₙ such that the subgraph of G induced by V_i has property P_i; i = 1,..., n. A hereditary property R is said to be reducible if there exist two hereditary properties P₁ and P₂ such that R = P₁∘P₂. 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 
@article{DMGT_1997_17_1_a1,
     author = {Broere, Izak and Frick, Marietjie and Semani\v{s}in, Gabriel},
     title = {Maximal graphs with respect to hereditary properties},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {51--66},
     publisher = {mathdoc},
     volume = {17},
     number = {1},
     year = {1997},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a1/}
}
TY  - JOUR
AU  - Broere, Izak
AU  - Frick, Marietjie
AU  - Semanišin, Gabriel
TI  - Maximal graphs with respect to hereditary properties
JO  - Discussiones Mathematicae. Graph Theory
PY  - 1997
SP  - 51
EP  - 66
VL  - 17
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a1/
LA  - en
ID  - DMGT_1997_17_1_a1
ER  - 
%0 Journal Article
%A Broere, Izak
%A Frick, Marietjie
%A Semanišin, Gabriel
%T Maximal graphs with respect to hereditary properties
%J Discussiones Mathematicae. Graph Theory
%D 1997
%P 51-66
%V 17
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a1/
%G en
%F DMGT_1997_17_1_a1
Broere, Izak; Frick, Marietjie; Semanišin, Gabriel. Maximal graphs with respect to hereditary properties. Discussiones Mathematicae. Graph Theory, Tome 17 (1997) no. 1, pp. 51-66. http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a1/