# Unique factorization theorem for object-systems

Peter Mihók; Gabriel Semanišin

Discussiones Mathematicae Graph Theory (2011)

- Volume: 31, Issue: 3, page 559-575
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topPeter Mihók, and Gabriel Semanišin. "Unique factorization theorem for object-systems." Discussiones Mathematicae Graph Theory 31.3 (2011): 559-575. <http://eudml.org/doc/270894>.

@article{PeterMihók2011,

abstract = {The concept of an object-system is a common generalization of simple graph, digraph and hypergraph. In the theory of generalised colourings of graphs, the Unique Factorization Theorem (UFT) for additive induced-hereditary properties of graphs provides an analogy of the well-known Fundamental Theorem of Arithmetics. The purpose of this paper is to present UFT for object-systems. This result generalises known UFT for additive induced-hereditary and hereditary properties of graphs and digraphs. Formal Concept Analysis is applied in the proof.},

author = {Peter Mihók, Gabriel Semanišin},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {object-system; unique factorization; graph; hypergraph; formal concept analysis},

language = {eng},

number = {3},

pages = {559-575},

title = {Unique factorization theorem for object-systems},

url = {http://eudml.org/doc/270894},

volume = {31},

year = {2011},

}

TY - JOUR

AU - Peter Mihók

AU - Gabriel Semanišin

TI - Unique factorization theorem for object-systems

JO - Discussiones Mathematicae Graph Theory

PY - 2011

VL - 31

IS - 3

SP - 559

EP - 575

AB - The concept of an object-system is a common generalization of simple graph, digraph and hypergraph. In the theory of generalised colourings of graphs, the Unique Factorization Theorem (UFT) for additive induced-hereditary properties of graphs provides an analogy of the well-known Fundamental Theorem of Arithmetics. The purpose of this paper is to present UFT for object-systems. This result generalises known UFT for additive induced-hereditary and hereditary properties of graphs and digraphs. Formal Concept Analysis is applied in the proof.

LA - eng

KW - object-system; unique factorization; graph; hypergraph; formal concept analysis

UR - http://eudml.org/doc/270894

ER -

## References

top- [1] A. Bonato, Homomorphism and amalgamation, Discrete Math. 270 (2003) 33-42, doi: 10.1016/S0012-365X(02)00864-6. Zbl1024.03046
- [2] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishwa International Publication, Gulbarga, 1991) 42-69.
- [3] 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. Zbl0902.05026
- [4] I. Broere and J. Bucko, Divisibility in additive hereditary properties and uniquely partitionable graphs, Tatra Mt. Math. Publ. 18 (1999) 79-87. Zbl0951.05034
- [5] 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. Zbl1013.05066
- [6] J. Bucko and P. Mihók, On uniquely partitionable systems of objects, Discuss. Math. Graph Theory 26 (2006) 281-289, doi: 10.7151/dmgt.1320. Zbl1142.05024
- [7] R. Cowen, S.H. Hechler and P. Mihók, Graph coloring compactness theorems equivalent to BPI, Scientia Math. Japonicae 56 (2002) 171-180. Zbl1023.05048
- [8] A. Farrugia, Uniqueness and complexity in generalised colouring., Ph.D. Thesis, University of Waterloo, April 2003 (available at http://etheses.uwaterloo.ca).
- [9] A. Farrugia, Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard, Elect. J. Combin. 11 (2004) R46, pp. 9 (electronic). Zbl1053.05046
- [10] A. Farrugia and R.B. Richter, Unique factorization of additive induced-hereditary properties, Discuss. Math. Graph Theory 24 (2004) 319-343, doi: 10.7151/dmgt.1234. Zbl1061.05070
- [11] A. Farrugia, P. Mihók, R.B. Richter and G. Semanišin, Factorizations and Characterizations of Induced-Hereditary and Compositive Properties, J. Graph Theory 49 (2005) 11-27, doi: 10.1002/jgt.20062. Zbl1067.05057
- [12] R. Fraïssé, Sur certains relations qui generalisent l'ordre des nombers rationnels, C.R. Acad. Sci. Paris 237 (1953) 540-542. Zbl0051.03803
- [13] R. Fraïssé, Theory of Relations (North-Holland, Amsterdam, 1986).
- [14] B. Ganter and R. Wille, Formal Concept Analysis - Mathematical Foundation (Springer-Verlag Berlin Heidelberg, 1999), doi: 10.1007/978-3-642-59830-2. Zbl0909.06001
- [15] W. Imrich, P. Mihók and G. Semanišin, A note on the unique factorization theorem for properties of infinite graphs, Stud. Univ. Zilina, Math. Ser. 16 (2003) 51-54. Zbl1056.05062
- [16] J. Jakubík, On the lattice of additive hereditary properties of finite graphs, Discuss. Math. - General Algebra and Applications 22 (2002) 73-86. Zbl1032.06003
- [17] T.R. Jensen and B. Toft, Graph Colouring Problems (Wiley-Interscience Publications, New York, 1995). Zbl0971.05046
- [18] 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. Zbl0949.05025
- [19] 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. Zbl0623.05043
- [20] P. Mihók, Unique factorization theorem, Discuss. Math. Graph Theory 20 (2000) 143-153, doi: 10.7151/dmgt.1114. Zbl0968.05032
- [21] P. Mihók, On the lattice of additive hereditary properties of object systems, Tatra Mt. Math. Publ. 30 (2005) 155-161. Zbl1150.05394
- [22] 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 Zbl0942.05056
- [23] P. Mihók and G. Semanišin, Unique Factorization Theorem and Formal Concept Analysis, B. Yahia et al. (Eds.): CLA 2006, LNAI 4923, (Springer-Verlag, Berlin Heidelberg 2008) 231-238. Zbl1133.05306
- [24] B.C. Pierce, Basic Category Theory for Computer Scientists, Foundations of Computing Series (The MIT Press, Cambridge, Massachusetts 1991).
- [25] N.W. Sauer, Canonical vertex partitions, Combinatorics, Probability and Computing 12 (2003) 671-704, doi: 10.1017/S0963548303005765. Zbl1062.03046
- [26] E.R. Scheinerman, On the Structure of Hereditary Classes of Graphs, J. Graph Theory 10 (1986) 545-551, doi: 10.1002/jgt.3190100414. Zbl0609.05057
- [27] R. Vasky, Unique factorization theorem for additive induced-hereditary properties of digraphs Studies of the University of Zilina, Mathematical Series 15 (2002) 83-96. Zbl1054.05047