ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory  17(1) (1997)   103-113
DOI: 10.7151/dmgt.1043


Jozef Bucko

Department of Geometry and Algebra, P.J. Šafárik University
Jesenná 5, 041 54 Košice, Slovak Republic


Marietjie Frick

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


Peter Mihók and Roman Vasky

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 of the vertex set V(G) into subsets V1, …,Vn such that the subgraph G[Vi] induced by Vi has property Pi; i = 1,…,n. A graph G is said to be uniquely (P1, …,Pn)-partitionable if G has exactly one (P1,…,Pn)-partition. A property P is called hereditary if every subgraph of every graph with property P also has property P. If every graph that is a disjoint union of two graphs that have property P also has property P, then we say that P is additive. A property P is called degenerate if there exists a bipartite graph that does not have property P. In this paper, we prove that if P1,…, Pn are degenerate, additive, hereditary properties of graphs, then there exists a uniquely (P1,…,Pn)-partitionable graph.

Keywords: hereditary property of graphs, additivity, reducibility, vertex partition.

1991 Mathematics Subject Classification: 05C15, 05C70.


[1] J.A. Andrews and M.S. Jacobson, On a generalization of chromatic number, Congressus Numerantium 47 (1985) 33-48.
[2] G. Benadé, I. Broere and J.I. Brown, A construction of uniquely C4-free colourable graphs, Questiones Mathematicae 13 (1990) 259-264, doi: 10.1080/16073606.1990.9631616.
[3] 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.
[4] B. Bollobás and N. Sauer, Uniquely colourable graphs with large girth, Canad. J. Math. 28 (1976) 1340-1344, doi: 10.4153/CJM-1976-133-5.
[5] B. Bollobás and A.G. Thomason, Uniquely partitionable graphs, J. London Math. Soc. 16 (1977) 403-410, doi: 10.1112/jlms/s2-16.3.403.
[6] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, eds., Advances in Graph Theory, (Vishwa International Publication, Gulbarga 1991) 42-69.
[7] 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.
[8] J.I. Brown and D.G. Corneil, On generalized graph colourings, J. Graph Theory 11 (1987) 86-99, doi: 10.1002/jgt.3190110113.
[9] J.I. Brown, D. Kelly, J. Schoenheim and R.E. Woodrow, Graph coloring satisfying restraints, Discrete Math. (1990) 123-143, doi: 10.1016/0012-365X(90)90113-V.
[10] S.A. Burr and M.S. Jacobson, On inequalities involving vertex-partition parameters of graphs, Congressus Numerantium 70 (1990) 159-170.
[11] L.J. Cowen, R.H. Cowen and D.R. Woodall, Defective colorings of graphs in surfaces; partitions into subgraphs of bounded valency, J. Graph Theory 10 (1986) 187-195, doi: 10.1002/jgt.3190100207.
[12] M. Frick, A survey of (m,k)-colourings, in: J. Gimbel c.a, eds., Quo Vadis,Graph Theory? Annals of Discrete Mathematics 55 (North-Holland, Amsterdam, 1993) 45-58.
[13] M. Frick and M.A. Henning, Extremal results on defective colorings of graph, Discrete Math. 126 (1994) 151-158, doi: 10.1016/0012-365X(94)90260-7.
[14] D. Gernet, Forbidden and unavoidable subgraphs, Ars Combinatoria 27 (1989) 165-176.
[15] R.L. Graham, M. Grötschel and L. Lovász, Handbook of Combinatorics (Elsevier Science B.V., Amsterdam 1995).
[16] D.L. Greenwell, R.L. Hemminger and J. Klerlein, Forbidden subgraphs, in: Proc. 4th S-E Conf. Combinatorics, Graph Theory and Computing, (Utilitas Math., Winnipeg, Man., 1973) 389-394.
[17] F. Harary, S.T. Hedetniemi and R.W. Robinson, Uniquely colourable graphs, J. Combin. Theory 6 (1969) 264-270, doi: 10.1016/S0021-9800(69)80086-4.
[18] G. Chartrand, D. Geller and S. Hedetniemi, Graphs with forbidden subgraphs, J. Combin. Theory (B) 10 (1971) 12-41, doi: 10.1016/0095-8956(71)90065-7.
[19] G. Chartrand and J.P. Geller, Uniquely colourable planar graphs, J. Combin. Theory 6 (1969) 271-278, doi: 10.1016/S0021-9800(69)80087-6.
[20] T.R. Jensen and B. Toft, Graph Colouring Problems (Wiley-Interscience Publications, New York 1995).
[21] R.P. Jones, Hereditary properties and P-chromatic number, in: T.P. McDonough and V.C. Marron, eds., Combinatorics, Proc. Brit. Comb. Conf. (London Math. Soc. Lecture Note Ser., No.13, Cambridge Univ. Press, London 1974) 83-88.
[22] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar 1 (1966) 237-238.
[23] 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.
[24] J. Mitchem, Maximal k-degenerate graphs, Utilitas Math. 11 (1977) 101-106.
[25] F.S. Roberts, From garbage to rainbows: generalizations of graph colouring and their applications, in: Y. Alavi, G. Chartrand, O.R. Oellermann, and A.J. Schwenk, eds., Graph Theory, Combinatorics and Applications, (Wiley, New York, 1991) 1031-1052.
[26] F.S. Roberts, New directions in graph theory (with an emphasis on the role of applications), in: J. Gimbel, J.W. Kennedy, and L.V. Quintas, eds., Quo Vadis Graph Theory, (North-Holland, Amsterdam, 1993) 13-44.
[27] J.M.S. Simoes-Pereira, Joins of n-degenerate graphs and uniquely (m,n)-partitionable graphs, J. Combin. Theory (B) 21 (1976) 21-29, doi: 10.1016/0095-8956(76)90023-X.
[28] 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.
[29] M. Simonovits, Extremal graph theory, in: L.W. Beineke and R.J. Wilson, eds., Selected Topics in Graph Theory, 2 (Academic Press, London, 1983) 161-200.
[30] M. Simonovits, Extremal graph problems and graph products, in: Studies in Pure Math. (dedicated to the memory of P. Turán) (1983) 669-680.
[31] M. Weaver and D.B. West, Relaxed chromatic numbers of graphs, Graphs and Combinatorics 10 (1994) 75-93, doi: 10.1007/BF01202473.
[32] D. Woodall, Improper colorings of graphs, in: R. Nelson and R.J. Wilson, eds., Graph Colorings (Longman, New York, 1990) 45-64.
[33] X. Zhu, Uniquely H-colorable graphs with large girth, J. Graph Theory 23 (1996) 33-41, doi: 10.1002/(SICI)1097-0118(199609)23:1<33::AID-JGT3>3.0.CO;2-L.