Discussiones
Mathematicae Graph Theory 19(2) (1999) 159-166
DOI: https://doi.org/10.7151/dmgt.1092
REMARKS ON THE EXISTENCE OF UNIQUELY PARTITIONABLE PLANAR GRAPHS
Mieczysław Borowiecki Institute of Mathematics |
Peter Mihók Faculty of Economics |
Zsolt Tuza Computer and Automation Institute |
M. Voigt Institute of Mathematics |
Abstract
We consider the problem of the existence of uniquely partitionable planar graphs. We survey some recent results and we prove the nonexistence of uniquely (D1,D1)-partitionable planar graphs with respect to the property D1 "to be a forest".
Keywords: property of graphs, additive, hereditary, vertex partition, uniquely partitionable graphs.
1991 Mathematics Subject Classification: 05C15, 05C35, O5C75.
References
[1] | C. Bazgan, M. Santha and Zs. Tuza, On the approximation of finding a(nother) Hamiltonian cycle in cubic Hamiltonian graphs, in: Proc. STACS'98, Lecture Notes in Computer Science 1373 (Springer-Verlag, 1998) 276-286. Extended version in the J. Algorithms 31 (1999) 249-268. |
[2] | C. Berge, Theorie des Graphes, Paris, 1958. |
[3] | C. Berge, Graphs and Hypergraphs, North-Holland, 1973. |
[4] | 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. |
[5] | M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, Survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. |
[6] | I. Broere and J. Bucko, Divisibility in additive hereditary graph properties and uniquely partitionable graphs, Tatra Mountains 18 (1999) 79-87. |
[7] | J. Bucko, M. Frick, P. Mihók and R. Vasky, Uniquely partitionable graphs, Discuss. Math. Graph Theory 17 (1997) 103-114, doi: 10.7151/dmgt.1043. |
[8] | J. Bucko and J. Ivanco, Uniquely partitionable planar graphs with respect to properties having a forbidden tree, Discuss. Math. Graph Theory 19 (1999) 71-78, doi: 10.7151/dmgt.1086. |
[9] | J. Bucko, P. Mihók and M. Voigt Uniquely partitionable planar graphs, Discrete Math. 191 (1998) 149-158, doi: 10.1016/S0012-365X(98)00102-2. |
[10] | 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. |
[11] | F. Harary, S.T. Hedetniemi and R.W. Robinson, Uniquely colourable graphs, J. Combin. Theory 6 (1969) 264-270; MR39#99. |
[12] | P. Mihók, Reducible properties and uniquely partitionable graphs, in: Contemporary Trends in Discrete Mathematics, From DIMACS and Dimatia to the Future, Proceedings of the DIMATIA-DIMACS Conference, Stirin May 1997, Ed. R.L. Graham, J. Kratochvil, J. Ne setril, F.S. Roberts, DIMACS Series in Discrete Mathematics, Volume 49, AMS, 213-218. |
[13] | P. Mihók, G. Semanišin and R. Vasky, Hereditary additive properties are uniquely factorizable into irreducible factors, J. Graph Theory 33 (2000)44-53, doi: 10.1002/(SICI)1097-0118(200001)33:1<44::AID-JGT5>3.0.CO;2-O. |
[14] | J. Mitchem, Uniquely k-arborable graphs, Israel J. Math. 10 (1971) 17-25; MR46#81. |
Received 2 February 1999
Revised 21 September 1999
Close