DMGT

Discussiones Mathematicae Graph Theory 22(1) (2002) 31-37
DOI: https://doi.org/10.7151/dmgt.1156

CRITERIA FOR OF THE EXISTENCE OF UNIQUELY PARTITIONABLE GRAPHS WITH RESPECT TO ADDITIVE INDUCED-HEREDITARY PROPERTIES

Izak Broere

Department of Mathematics
Rand Afrikaans University
P.O. Box 524, Auckland Park, 2006 South Africa
e-mail: ib@na.rau.ac.za

Jozef Bucko

Department of Applied Mathematics
Faculty of Economics, Technical University
B. Nemcovej, 040 01 Košice, Slovak Republic
e-mail: bucko@tuke.sk

Peter Mihók

Department of Applied Mathematics
Faculty of Economics, Technical University
B. Nemcovej, 040 01 Košice, Slovak Republic
and
Mathematical Institute, Slovak Academy of Science
Gresákova 6, 040 01 Košice, Slovak Republic
e-mail: mihokp@tuke.sk

Abstract

Let P₁,P₂,...,P_n be graph properties, a graph G is said to be uniquely (P₁, P₂, …,P_n)-partitionable if there is exactly one (unordered) partition {V₁,V₂, …,V_n} of V(G) such that G[V_i] ∈ P_i for i = 1,2,...,n. We prove that for additive and induced-hereditary properties uniquely (P₁, P₂, …,P_n)-partitionable graphs exist if and only if P_i and P_j are either coprime or equal irreducible properties of graphs for every i ≠ j, i,j ∈ {1,2,...,n}.

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

2000 Mathematics Subject Classification: 05C15, 05C75.

References

[1]	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.
[3]	I. Broere and J. Bucko, Divisibility in additive hereditary graph properties and uniquely partitionable graphs, Tatra Mt. Math. Publ. 18 (1999) 79-87.
[4]	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.
[5]	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.
[6]	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.
[7]	P. Mihók, Unique factorization theorem, Discuss. Math. Graph Theory 20 (2000) 143-154, doi: 10.7151/dmgt.1114.

Received 8 August 2000
Revised 2 July 2001