Remarks on the existence of uniquely partitionable planar graphs

• Autorzy: Mieczysław Borowiecki , Peter Mihók , Zsolt Tuza , M. Voigt
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

property of graphs; additive; hereditary; vertex partition; uniquely partitionable graphs

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs
• 05C35: Extremal problems

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1999
• Tom: 19
• Numer: 2
• Strony: 159-166

Daty

wydano

1999

otrzymano

1999-02-02

poprawiono

1999-09-21

Twórcy

autor

Mieczysław Borowiecki

• Institute of Mathematics, Technical University Zielona Góra, Poland

autor

Peter Mihók

• Faculty of Economics, Technical University Košice, Slovakia

autor

Zsolt Tuza

• Computer and Automation Institute, Hungarian Academy of Sciences Budapest, Hungary

autor

M. Voigt

• Institute of Mathematics, Technical University Ilmenau, Germany

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgt.1092