ArticleOriginal scientific text

Title

On infinite uniquely partitionable graphs and graph properties of finite character

Authors 1, 1, 2

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, Gresákova 6, 040 01 Košice, Slovak Republic

Abstract

A graph property is any nonempty isomorphism-closed class of simple (finite or infinite) graphs. A graph property is of finite character if a graph G has a property if and only if every finite induced subgraph of G has a property . Let ₁,₂,...,ₙ be graph properties of finite character, a graph G is said to be (uniquely) (₁, ₂, ...,ₙ)-partitionable if there is an (exactly one) partition {V₁, V₂, ..., Vₙ} of V(G) such that G[Vi]i for i = 1,2,...,n. Let us denote by ℜ = ₁ ∘ ₂ ∘ ... ∘ ₙ the class of all (₁,₂,...,ₙ)-partitionable graphs. A property ℜ = ₁ ∘ ₂ ∘ ... ∘ ₙ, n ≥ 2 is said to be reducible. We prove that any reducible additive graph property ℜ of finite character has a uniquely (₁, ₂, ...,ₙ)-partitionable countable generating graph. We also prove that for a reducible additive hereditary graph property ℜ of finite character there exists a weakly universal countable graph if and only if each property _i has a weakly universal graph.

Keywords

graph property of finite character, reducibility, uniquely partitionable graphs, weakly universal graph

Bibliography

  1. M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, Survey of hereditary graph properties, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037.
  2. I. Broere and J. Bucko, Divisibility in additive hereditary graph properties and uniquely partitionable graphs, Tatra Mt. Math. Publ. 18 (1999) 79-87.
  3. 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.
  4. J. Bucko, M. Frick, P. Mihók and R. Vasky, Uniquely partitionable graphs, Discuss. Math. Graph Theory 17 (1997) 103-114, doi: 10.7151/dmgt.1043.
  5. G. Cherlin, S. Shelah and N. Shi, Universal graphs with forbidden subgraphs and algebraic closure, Advances in Appl. Math. 22 (1999) 454-491, doi: 10.1006/aama.1998.0641.
  6. R. Cowen, S.H. Hechler and P. Mihók, Graph coloring compactness theorems equivalent to BPI, Scientia Math. Japonicae 56 (2002) 171-180.
  7. 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.
  8. B. Ganter and R. Wille, Formal Concept Analysis - Mathematical Foundation (Springer-Verlag Berlin Heidelberg, 1999), doi: 10.1007/978-3-642-59830-2.
  9. R.L. Graham, M. Grotschel and L. Lovasz, Handbook of Combinatorics (Elsevier Science B.V., Amsterdam, 1995).
  10. F. Harary, S.T. Hedetniemi and R.W. Robinson, Uniquely colourable graphs, J. Combin. Theory 6 (1969) 264-270, doi: 10.1016/S0021-9800(69)80086-4.
  11. 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.
  12. 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.
  13. P. Mihók, Unique factorization theorem, Discuss. Math. Graph Theory 20 (2000) 143-154, doi: 10.7151/dmgt.1114.
  14. P. Mihók, On the lattice of additive hereditary properties of object systems, Tatra Mt. Math. Publ. 30 (2005) 155-161.
  15. P. Mihók and G. Semanišin, Unique Factorization Theorem and Formal Concept Analysis, CLA 2006, Yasmin, Hammamet, Tunisia, (2006), 195-203.
  16. N.W. Sauer, Canonical vertex partitions, Combinatorics, Probability and Computing 12 (2003) 671-704, doi: 10.1017/S0963548303005765.
  17. E.R. Scheinerman, On the structure of hereditary classes of graphs, J. Graph Theory 10 (1986) 545-551, doi: 10.1002/jgt.3190100414.
Pages:
241-251
Main language of publication
English
Received
2007-12-31
Accepted
2008-11-27
Published
2009
Exact and natural sciences