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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.