# Maximal graphs with respect to hereditary properties

Izak Broere; Marietjie Frick; Gabriel Semanišin

Discussiones Mathematicae Graph Theory (1997)

- Volume: 17, Issue: 1, page 51-66
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topIzak Broere, Marietjie Frick, and Gabriel Semanišin. "Maximal graphs with respect to hereditary properties." Discussiones Mathematicae Graph Theory 17.1 (1997): 51-66. <http://eudml.org/doc/270401>.

@article{IzakBroere1997,

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 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 Vi 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.},

author = {Izak Broere, Marietjie Frick, Gabriel Semanišin},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {hereditary property of graphs; maximal graphs; vertex partition; hereditary property; reducible property; -degenerate graph},

language = {eng},

number = {1},

pages = {51-66},

title = {Maximal graphs with respect to hereditary properties},

url = {http://eudml.org/doc/270401},

volume = {17},

year = {1997},

}

TY - JOUR

AU - Izak Broere

AU - Marietjie Frick

AU - Gabriel Semanišin

TI - Maximal graphs with respect to hereditary properties

JO - Discussiones Mathematicae Graph Theory

PY - 1997

VL - 17

IS - 1

SP - 51

EP - 66

AB - 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 Vi 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.

LA - eng

KW - hereditary property of graphs; maximal graphs; vertex partition; hereditary property; reducible property; -degenerate graph

UR - http://eudml.org/doc/270401

ER -

## References

top- [1] G. Benadé, I. Broere, B. Jonck and M. Frick, Uniquely ${(m,k)}^{\tau}$-colourable graphs and k-τ-saturated graphs, Discrete Math. 162 (1996) 13-22, doi: 10.1016/0012-365X(95)00301-C. Zbl0870.05026
- [2] M. Borowiecki, I. Broere and P. Mihók, Minimal reducible bounds for planar graphs, submitted. Zbl0945.05022
- [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. Zbl0813.05061
- [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. Zbl0906.05058
- [6] G. Chartrand and L. Lesniak, Graphs and Digraphs, (Wadsworth & Brooks/Cole, Monterey California, 1986). Zbl0666.05001
- [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. Zbl0101.41001
- [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. Zbl0129.39901
- [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. Zbl0593.05041
- [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. Zbl0905.05038
- [12] R. Lick and A.T. White, k-degenerate graphs, Canad. J. Math. 22 (1970) 1082-1096; MR42#1715. Zbl0202.23502
- [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. Zbl0623.05043
- [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. Zbl0829.05057
- [15] J. Mitchem, An extension of Brooks' theorem to r-degenerate graphs, Discrete Math. 17 (1977) 291-298; MR 55#12561. Zbl0351.05124
- [16] J. Mitchem, Maximal k-degenerate graphs, Utilitas Math. 11 (1977) 101-106. Zbl0348.05109
- [17] G. Semanišin, On some variations of extremal graph problems, Discussiones Mathematicae Graph Theory 17 (1997) 67-76, doi: 10.7151/dmgt.1039. Zbl0904.05046
- [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. Zbl0331.05135

## Citations in EuDML Documents

top- Jan Kratochvíl, Peter Mihók, Gabriel Semanišin, Graphs maximal with respect to hom-properties
- Bohdan Zelinka, Graphs maximal with respect to absence of hamiltonian paths
- Izak Broere, Marietjie Frick, Peter Mihók, The order of uniquely partitionable graphs
- Ewa Drgas-Burchardt, A note on joins of additive hereditary graph properties
- Alastair Farrugia, R. Bruce Richter, Unique factorisation of additive induced-hereditary properties
- Izak Broere, Michael Dorfling, Jean E. Dunbar, Marietjie Frick, A path(ological) partition problem
- Marietjie Frick, A Survey of the Path Partition Conjecture
- Mieczysław Borowiecki, Izak Broere, Marietjie Frick, Peter Mihók, Gabriel Semanišin, A survey of hereditary properties of graphs

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.