Download PDF - Unique factorization theorem for object-systemsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Unique factorization theorem for object-systems

Authors 1, 2, 3

Affiliations

  1. Department of Applied Mathematics, Faculty of Economics, Technical University, B. Nĕmcovej, 040 01 Košice, Slovak Republic
  2. Mathematical Institute, Slovak Academy of Science, Grešákova 6, 040 01 Košice, Slovak Republic
  3. Institute of Computer Science, P.J. Šafárik University, Faculty of Science, Jesenná 5, 041 54 Košice, Slovak Republic

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

ENG
object-system, unique factorization, graph, hypergraph, formal concept analysis

Bibliography

  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.
Discussiones Mathematicae Graph Theory
2011/31/3
Export to PBN, Opens in new tab
Pages:
559-575
Main language of publication
English
Received
2010-04-07
Accepted
2010-08-21
Published
2011

DOI: 10.7151/dmgt.1565

Exact and natural sciences