ArticleOriginal scientific text

Title

Uniquely partitionable planar graphs with respect to properties having a forbidden tree

Authors 1, 2

Affiliations

  1. Department of Mathematics, Technical University, Hlavná 6, 040 01 Košice, Slovak Republic
  2. Department of Geometry and Algebra, P.J. Šafárik University, Jesenná 5, 041 54 Košice, Slovak Republic

Abstract

Let ₁, ₂ be graph properties. A vertex (₁,₂)-partition of a graph G is a partition {V₁,V₂} of V(G) such that for i = 1,2 the induced subgraph G[Vi] has the property _i. A property ℜ = ₁∘₂ is defined to be the set of all graphs having a vertex (₁,₂)-partition. A graph G ∈ ₁∘₂ is said to be uniquely (₁,₂)-partitionable if G has exactly one vertex (₁,₂)-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

Bibliography

  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.
Pages:
71-78
Main language of publication
English
Received
1998-07-14
Accepted
1998-11-24
Published
1999
Exact and natural sciences