Geodesic
Unique factorization theorem for object-systems
Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 3, pp. 559-575.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: object-system, unique factorization, graph, hypergraph, formal concept analysis 
@article{DMGT_2011_31_3_a10,
     author = {Mih\'ok, Peter and Semani\v{s}in, Gabriel},
     title = {Unique factorization theorem for object-systems},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {559--575},
     publisher = {mathdoc},
     volume = {31},
     number = {3},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a10/}
}
TY  - JOUR
AU  - Mihók, Peter
AU  - Semanišin, Gabriel
TI  - Unique factorization theorem for object-systems
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2011
SP  - 559
EP  - 575
VL  - 31
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a10/
LA  - en
ID  - DMGT_2011_31_3_a10
ER  - 
%0 Journal Article
%A Mihók, Peter
%A Semanišin, Gabriel
%T Unique factorization theorem for object-systems
%J Discussiones Mathematicae. Graph Theory
%D 2011
%P 559-575
%V 31
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a10/
%G en
%F DMGT_2011_31_3_a10
Mihók, Peter; Semanišin, Gabriel. Unique factorization theorem for object-systems. Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 3, pp. 559-575. http://geodesic.mathdoc.fr/item/DMGT_2011_31_3_a10/

[1] A. Bonato, Homomorphism and amalgamation, Discrete Math. 270 (2003) 33-42, doi: 10.1016/S0012-365X(02)00864-6.

[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.

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

[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.

[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.

[7] R. Cowen, S.H. Hechler and P. Mihók, Graph coloring compactness theorems equivalent to BPI, Scientia Math. Japonicae 56 (2002) 171-180.

[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).

[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.

[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.

[12] R. Fraïssé, Sur certains relations qui generalisent l'ordre des nombers rationnels, C.R. Acad. Sci. Paris 237 (1953) 540-542.

[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.

[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.

[16] J. Jakubík, On the lattice of additive hereditary properties of finite graphs, Discuss. Math. - General Algebra and Applications 22 (2002) 73-86.

[17] T.R. Jensen and B. Toft, Graph Colouring Problems (Wiley-Interscience Publications, New York, 1995).

[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.

[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.

[20] P. Mihók, Unique factorization theorem, Discuss. Math. Graph Theory 20 (2000) 143-153, doi: 10.7151/dmgt.1114.

[21] P. Mihók, On the lattice of additive hereditary properties of object systems, Tatra Mt. Math. Publ. 30 (2005) 155-161.

[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:144::AID-JGT5>3.0.CO;2-O

[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.

[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.

[26] E.R. Scheinerman, On the Structure of Hereditary Classes of Graphs, J. Graph Theory 10 (1986) 545-551, doi: 10.1002/jgt.3190100414.

[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.