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 (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 22(1) (2002) 31-37
DOI: 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 P1,P2,...,Pn be graph properties, a graph G is said to be uniquely (P1, P2, …,Pn)-partitionable if there is exactly one (unordered) partition {V1,V2, …,Vn} of V(G) such that G[Vi] ∈ Pi for i = 1,2,...,n. We prove that for additive and induced-hereditary properties uniquely (P1, P2, …,Pn)-partitionable graphs exist if and only if Pi and Pj 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