ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

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

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory  17(1) (1997)   115-125
DOI: 10.7151/dmgt.1044


Izak Broere

Department of Mathematics
Rand Afrikaans University
P.O. Box 524, Aucklandpark, 2006 South Africa

Marietjie Frick

Department of Mathematics, Applied Mathematics and Astronomy
University of South Africa
P.O. Box 392, Pretoria, 0001 South Africa

Peter Mihók

Department of Geometry and Algebra
P.J. Šafárik University
Jesenná 5, 041 54 Košice, Slovak Republic
e-mail: mihok@Koš


Let P1, ..., Pn be properties of graphs. A (P1, Ľ, Pn)-partition of a graph G is a partition {V1, ...,Vn} of V(G) such that, for each i = 1,..., n, the subgraph of G induced by Vi has property Pi. If a graph G has a unique (P1, ..., Pn)-partition we say it is uniquely (P1, ..., Pn)-partitionable. We establish best lower bounds for the order of uniquely (P1, ...,  Pn)-partitionable graphs, for various choices of P1, ..., Pn.

Keywords: hereditary property of graphs, uniquely partitionable graphs.

1991 Mathematics Subject Classification: 05C15, 05C70.



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.


M. Borowiecki, P. Mihók, Hereditary properties of graphs, in: Advances in Graph Theory (Vishwa Internat. Publ., 1991) 41-68.


I. Broere and M. Frick, On the order of uniquely (k,m)-colourable graphs, Discrete Math. 82 (1990) 225-232, doi: 10.1016/0012-365X(90)90200-2.


I. Broere, M. Frick and G. Semanišin, Maximal graphs with respect to hereditary properties, Discussiones Mathematicae Graph Theory 17 (1997) 51-66, doi: 10.7151/dmgt.1038.


G. Chartrand and L. Lesniak, Graphs and Digraphs (Second Edition, Wadsworth & Brooks/Cole, Monterey, 1986).


M. Frick, On replete graphs, J. Graph Theory 16 (1992) 165-175, doi: 10.1002/jgt.3190160208.


M. Frick and M.A. Henning, Extremal results on defective colourings of graphs, Discrete Math. 126 (1994) 151-158, doi: 10.1016/0012-365X(94)90260-7.


P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: Graphs, Hypergraphs and Matroids (Zielona Góra, 1985) 49-58.


P. Mihók and G. Semanišin, Reducible properties of graphs, Discussiones Math. Graph Theory 15 (1995) 11-18, doi: 10.7151/dmgt.1002.