DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

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

PDF

Discussiones Mathematicae Graph Theory 19(2) (1999) 159-166
DOI: 10.7151/dmgt.1092

REMARKS ON THE EXISTENCE OF UNIQUELY PARTITIONABLE PLANAR GRAPHS

Mieczysław Borowiecki

Institute of Mathematics
Technical University Zielona Góra, Poland
e-mail: m.borowiecki@im.uz.zgora.pl

Peter Mihók

Faculty of Economics
Technical University Košice, Slovakia
e-mail: mihok@Košice.upjs.sk

Zsolt Tuza

Computer and Automation Institute
Hungarian Academy of Sciences Budapest, Hungary

e-mail: tuza@lutra.sztaki.hu

M. Voigt

Institute of Mathematics
Technical University Ilmenau, Germany
e-mail: voigt@mathematik.tu-ilmenau.de

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