Criteria for of the existence of uniquely partitionable graphs with respect to additive induced-hereditary properties

Izak Broere; Jozef Bucko; Peter Mihók

ArticleOriginal scientific text

Title

Criteria for of the existence of uniquely partitionable graphs with respect to additive induced-hereditary properties

Authors ¹, ², ^2,³

Affiliations

Department of Mathematics, Rand Afrikaans University, P.O. Box 524, Auckland Park, 2006 South Africa
Department of Applied Mathematics, Faculty of Economics, Technical University, B. Nĕmcovej, 040 01 Košice, Slovak Republic
Mathematical Institute, Slovak Academy of Science, Gresákova 6, 040 01 Košice, Slovak Republic

Abstract

Let ₁,₂,...,ₙ be graph properties, a graph G is said to be uniquely (₁,₂, ...,ₙ)-partitionable if there is exactly one (unordered) partition {V₁,V₂,...,Vₙ} of V(G) such that

G [V_{i}] \in_{i}

for i = 1,2,...,n. We prove that for additive and induced-hereditary properties uniquely (₁,₂,...,ₙ)-partitionable graphs exist if and only if

_i

and

_j

are either coprime or equal irreducible properties of graphs for every i ≠ j, i,j ∈ {1,2,...,n}.

Keywords

ENG

induced-hereditary properties, reducibility, divisibility, uniquely partitionable graphs.

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.
I. Broere and J. Bucko, Divisibility in additive hereditary graph properties and uniquely partitionable graphs, Tatra Mt. Math. Publ. 18 (1999) 79-87.
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.
F. Harary, S.T. Hedetniemi and R.W. Robinson, Uniquely colourable graphs, J. Combin. Theory 6 (1969) 264-270, doi: 10.1016/S0021-9800(69)80086-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.
P. Mihók, Unique factorization theorem, Discuss. Math. Graph Theory 20 (2000) 143-154, doi: 10.7151/dmgt.1114.

Title

Criteria for of the existence of uniquely partitionable graphs with respect to additive induced-hereditary properties

Affiliations

Abstract

Keywords

Bibliography