DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 19(1) (1999) 71-78
DOI: 10.7151/dmgt.1086

UNIQUELY PARTITIONABLE PLANAR GRAPHS WITH RESPECT TO PROPERTIES HAVING A FORBIDDEN TREE

Jozef Bucko

Department of Mathematics, Technical University
Hlavná 6, 040 01 Košice, Slovak Republic

e-mail: bucko@ccsun.tuke.sk

Jaroslav Ivančo

Department of Geometry and Algebra
P.J. Safárik University, Jesenná 5
041 54 Košice, Slovak Republic

e-mail: ivanco@duro.upjs.sk

Abstract

Let P1, P2 be graph properties. A vertex (P1,P2)-partition of a graph G is a partition { V1,V 2} of V(G) such that for i = 1,2 the induced subgraph G[Vi] has the property Pi. A property ℜ = P1 ºP2 is defined to be the set of all graphs having a vertex (P1,P2)-partition. A graph G ∈ P1ºP2 is said to be uniquely (P1,P2)-partitionable if G has exactly one vertex (P1,P2)-partition. In this note, we show the existence of uniquely partitionable planar graphs with respect to hereditary additive properties having a forbidden tree.

Keywords: uniquely partitionable planar graphs, forbidden graphs.

1991 Mathematics Subject Classification: 05C15, 05C70.

References

[1] 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.
[2] 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.
[3] M. Borowiecki, J. Bucko, P. Mihók, Z. Tuza and M. Voigt, Remarks on the existence of uniquely partitionable planar graphs, 13. Workshop on Discrete Optimization, Burg, abstract, 1998.
[4] P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: M. Borowiecki and Z. Skupień, eds., Graphs, hypergraphs and matroids (Zielona Góra, 1985) 49-58.

Received 14 July 1998
Revised 24 November 1998