Criteria for of the existence of uniquely partitionable graphs with respect to additive induced-hereditary properties
Izak Broere ; Jozef Bucko ; Peter Mihók
Discussiones Mathematicae Graph Theory, Tome 22 (2002), p. 31-37 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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[Vi]∈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.

Publié le : 2002-01-01
EUDML-ID : urn:eudml:doc:270442 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1156,
     author = {Izak Broere and Jozef Bucko and Peter Mih\'ok},
     title = {Criteria for of the existence of uniquely partitionable graphs with respect to additive induced-hereditary properties},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {22},
     year = {2002},
     pages = {31-37},
     zbl = {1013.05066},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1156}
}

Izak Broere; Jozef Bucko; Peter Mihók. Criteria for of the existence of uniquely partitionable graphs with respect to additive induced-hereditary properties. Discussiones Mathematicae Graph Theory, Tome 22 (2002) pp. 31-37. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1156/

[000] [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. | Zbl 0902.05026

[001] [3] I. Broere and J. Bucko, Divisibility in additive hereditary graph properties and uniquely partitionable graphs, Tatra Mt. Math. Publ. 18 (1999) 79-87. | Zbl 0951.05034

[002] [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. | Zbl 0906.05057

[003] [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. | Zbl 0175.50205

[004] [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. | Zbl 0623.05043

[005] [7] P. Mihók, Unique factorization theorem, Discuss. Math. Graph Theory 20 (2000) 143-154, doi: 10.7151/dmgt.1114. | Zbl 0968.05032