Discussiones Mathematicae Graph Theory 26(2) (2006)
281-289
DOI: https://doi.org/10.7151/dmgt.1320
ON UNIQUELY PARTITIONABLE RELATIONAL STRUCTURES AND OBJECT SYSTEMS
Jozef Bucko
Department of Applied Mathematics | Peter Mihók
Department of Applied Mathematics and |
Abstract
We introduce object systems as a common generalization of graphs, hypergraphs, digraphs and relational structures. Let C be a concrete category, a simple object system over C is an ordered pair S = (V,E), where E = {A1,A2,...,Am} is a finite set of the objects of C, such that the ground-set V(Ai) of each object Ai ∈ E is a finite set with at least two elements and V ⊇ ∪i = 1m V(Ai). To generalize the results on graph colourings to simple object systems we define, analogously as for graphs, that an additive induced-hereditary property of simple object systems over a category C is any class of systems closed under isomorphism, induced-subsystems and disjoint union of systems, respectively. We present a survey of recent results and conditions for object systems to be uniquely partitionable into subsystems of given properties.Keywords: graph, digraph, hypergraph, vertex colouring, uniquely partitionable system.
2000 Mathematics Subject Classification: 05C15, 05C20, 05C65, 05C75.
References
[1] | D. Achlioptas, J.I. Brown, D.G. Corneil and M.S.O. Molloy, The existence of uniquely − G colourable graphs, Discrete Math. 179 (1998) 1-11, doi: 10.1016/S0012-365X(97)00022-8. |
[2] | B. Bollobás and A. G. Thomason, Uniquely partitionable graphs, J. London Math. Soc. (2) 16 (1977) 403-410. |
[3] | A. Bonato, Homomorphism and amalgamation, Discrete Math. 270 (2003) 33-42, doi: 10.1016/S0012-365X(02)00864-6. |
[4] | 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. |
[5] | J. I. Brown and D. G. Corneil, On generalized graph colourings, J. Graph Theory 11 (1987) 86-99, doi: 10.1002/jgt.3190110113. |
[6] | I. Broere, J. Bucko and P. Mihók, Criteria for the existence of uniquely partitionable graphs with respect to additive induced-hereditary properties, Discuss. Math. Graph Theory 22 (2002) 31-37, doi: 10.7151/dmgt.1156. |
[7] | A. Farrugia, Uniqueness and complexity in generalised colouring, Ph.D. thesis, University of Waterloo, April 2003 (available at http://etheses.uwaterloo.ca). |
[8] | A. Farrugia, P. Mihók, R.B. Richter and G. Semanišin, Factorisations and characterisations of induced-hereditary and compositive properties, J. Graph Theory 49 (2005) 11-27, doi: 10.1002/jgt.20062. |
[9] | A. Farrugia and R.B. Richter, Unique factorisation of additive induced-hereditary properties, Discuss. Math. Graph Theory 24 (2004) 319-343, doi: 10.7151/dmgt.1234. |
[10] | R. Fraïssé, Sur certains relations qui generalisent l'ordre des nombers rationnels, C.R. Acad. Sci. Paris 237 (1953) 540-542. |
[11] | R. Fraïssé, Theory of Relations (North-Holland, Amsterdam, 1986). |
[12] | 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. |
[13] | J. Jakubík, On the lattice of additive hereditary properties of finite graphs, Discuss. Math. General Algebra and Applications 22 (2002) 73-86. |
[14] | J. Kratochvíl and P. Mihók, Hom-properties are uniquely factorizable into irreducible factors, Discrete Math. 213 (2000) 189-194, doi: 10.1016/S0012-365X(99)00179-X. |
[15] | P. Mihók, On the lattice of additive hereditary properties of object-systems, Tatra Mountains Math. Publ. 30 (2005) 155-161. |
[16] | 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. |
[17] | P. Mihók, Reducible properties and uniquely partitionable graphs, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 49 (1999) 213-218. |
[18] | P. Mihók Unique factorization theorems, Discuss. Math. Graph Theory 20 (2000) 143-153, doi: 10.7151/dmgt.1114. |
[19] | P. Mihók, G. Semanišin and R. Vasky, Additive and Hereditary Properties of Graphs are Uniquely Factorizable into Irreducible Factors, J. Graph Theory 33 (2000) 44-53, doi: 10.1002/(SICI)1097-0118(200001)33:1<44::AID-JGT5>3.0.CO;2-O. |
[20] | J. Mitchem, Uniquely k-arborable graphs, Israel J. Math. 10 (1971) 17-25, doi: 10.1007/BF02771516. |
[21] | B.C. Pierce, Basic Category Theory for Computer Scientists (Foundations of Computing Series, The MIT Press, Cambridge, Massachusetts 1991). |
[22] | J.M.S. Simoes-Pereira, On graphs uniquely partitionable into n-degenerate subgraphs, in: Infinite and Finite Sets, Colloquia Math. Soc. J. Bólyai 10 (1975) 1351-1364. |
[23] | R. Vasky, Unique factorization theorem for additive induced-hereditary properties of digraphs Studies of the University of Zilina, Mathematical Series 15 (2002) 83-96. |
Received 31 January 2005
Revised 2 December 2005
Close