DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 31(3) (2011) 559-575
DOI: https://doi.org/10.7151/dmgt.1565

UNIQUE FACTORIZATION THEOREM FOR OBJECT-SYSTEMS

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: peter.mihok@tuke.sk

Gabriel Semanišin

Institute of Computer Science
P.J. Safárik University, Faculty of Science
Jesenná 5, 041 54 Košice, Slovak Republic
e-mail: gabriel.semanisin@upjs.sk

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.

Keywords: object-system, unique factorization, graph, hypergraph, formal concept analysis.

2010 Mathematics Subject Classification: 05C15, 05C75.

References

[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:1<44::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.

Received 7 April 2010
Revised 21 August 2010
Accepted 27 August 2010

Close