PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2011 | 31 | 3 | 559-575
Tytuł artykułu

Unique factorization theorem for object-systems

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
31
Numer
3
Strony
559-575
Opis fizyczny
Daty
wydano
2011
otrzymano
2010-04-07
poprawiono
2010-08-21
zaakceptowano
2010-08-27
Twórcy
autor
  • Department of Applied Mathematics, Faculty of Economics, Technical University, B. Nĕmcovej, 040 01 Košice, Slovak Republic
  • Mathematical Institute, Slovak Academy of Science, Grešákova 6, 040 01 Košice, Slovak Republic
  • Institute of Computer Science, P.J. Šafárik University, Faculty of Science, Jesenná 5, 041 54 Košice, Slovak Republic
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1565
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.