Remarks on the existence of uniquely partitionable planar graphs
Mieczysław Borowiecki ; Peter Mihók ; Zsolt Tuza ; M. Voigt
Discussiones Mathematicae Graph Theory, Tome 19 (1999), p. 159-166 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

We consider the problem of the existence of uniquely partitionable planar graphs. We survey some recent results and we prove the nonexistence of uniquely (𝓓₁,𝓓₁)-partitionable planar graphs with respect to the property 𝓓₁ "to be a forest".

Publié le : 1999-01-01
EUDML-ID : urn:eudml:doc:270347 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1092,
     author = {Mieczys\l aw Borowiecki and Peter Mih\'ok and Zsolt Tuza and M. Voigt},
     title = {Remarks on the existence of uniquely partitionable planar graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {19},
     year = {1999},
     pages = {159-166},
     zbl = {0958.05118},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1092}
}

Mieczysław Borowiecki; Peter Mihók; Zsolt Tuza; M. Voigt. Remarks on the existence of uniquely partitionable planar graphs. Discussiones Mathematicae Graph Theory, Tome 19 (1999) pp. 159-166. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1092/

[000] [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.

[001] [2] C. Berge, Theorie des Graphes, Paris, 1958.

[002] [3] C. Berge, Graphs and Hypergraphs, North-Holland, 1973.

[003] [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. | Zbl 0377.05038

[004] [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. | Zbl 0902.05026

[005] [6] I. Broere and J. Bucko, Divisibility in additive hereditary graph properties and uniquely partitionable graphs, Tatra Mountains 18 (1999) 79-87. | Zbl 0951.05034

[006] [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. | Zbl 0906.05057

[007] [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. | Zbl 0944.05080

[008] [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. | Zbl 0957.05029

[009] [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. | Zbl 0175.50206

[010] [11] F. Harary, S.T. Hedetniemi and R.W. Robinson, Uniquely colourable graphs, J. Combin. Theory 6 (1969) 264-270; MR39#99. | Zbl 0175.50205

[011] [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.

[012] [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 | Zbl 0942.05056

[013] [14] J. Mitchem, Uniquely k-arborable graphs, Israel J. Math. 10 (1971) 17-25; MR46#81. | Zbl 0224.05105