Remarks on the existence of uniquely partitionable planar graphs

Mieczysław Borowiecki; Peter Mihók; Zsolt Tuza; M. Voigt

Discussiones Mathematicae Graph Theory (1999)

  • Volume: 19, Issue: 2, page 159-166
  • ISSN: 2083-5892

Abstract

top
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".

How to cite

top

Mieczysław Borowiecki, et al. "Remarks on the existence of uniquely partitionable planar graphs." Discussiones Mathematicae Graph Theory 19.2 (1999): 159-166. <http://eudml.org/doc/270347>.

@article{MieczysławBorowiecki1999,
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 (𝓓₁,𝓓₁)-partitionable planar graphs with respect to the property 𝓓₁ "to be a forest".},
author = {Mieczysław Borowiecki, Peter Mihók, Zsolt Tuza, M. Voigt},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {property of graphs; additive; hereditary; vertex partition; uniquely partitionable graphs; uniquely partitionable planar graphs; planar graphs},
language = {eng},
number = {2},
pages = {159-166},
title = {Remarks on the existence of uniquely partitionable planar graphs},
url = {http://eudml.org/doc/270347},
volume = {19},
year = {1999},
}

TY - JOUR
AU - Mieczysław Borowiecki
AU - Peter Mihók
AU - Zsolt Tuza
AU - M. Voigt
TI - Remarks on the existence of uniquely partitionable planar graphs
JO - Discussiones Mathematicae Graph Theory
PY - 1999
VL - 19
IS - 2
SP - 159
EP - 166
AB - 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".
LA - eng
KW - property of graphs; additive; hereditary; vertex partition; uniquely partitionable graphs; uniquely partitionable planar graphs; planar graphs
UR - http://eudml.org/doc/270347
ER -

References

top
  1. [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. [2] C. Berge, Theorie des Graphes, Paris, 1958. 
  3. [3] C. Berge, Graphs and Hypergraphs, North-Holland, 1973. 
  4. [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. Zbl0377.05038
  5. [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. Zbl0902.05026
  6. [6] I. Broere and J. Bucko, Divisibility in additive hereditary graph properties and uniquely partitionable graphs, Tatra Mountains 18 (1999) 79-87. Zbl0951.05034
  7. [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. Zbl0906.05057
  8. [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. Zbl0944.05080
  9. [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. Zbl0957.05029
  10. [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. Zbl0175.50206
  11. [11] F. Harary, S.T. Hedetniemi and R.W. Robinson, Uniquely colourable graphs, J. Combin. Theory 6 (1969) 264-270; MR39#99. Zbl0175.50205
  12. [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. [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 Zbl0942.05056
  14. [14] J. Mitchem, Uniquely k-arborable graphs, Israel J. Math. 10 (1971) 17-25; MR46#81. Zbl0224.05105

NotesEmbed ?

top

You must be logged in to post comments.