PDF

Discussiones Mathematicae Graph Theory 29(2) (2009) 241-251
DOI: https://doi.org/10.7151/dmgt.1444

ON INFINITE UNIQUELY PARTITIONABLE GRAPHS AND GRAPH PROPERTIES OF FINITE CHARACTER

Jozef Bucko Department of Applied Mathematics Faculty of Economics, Technical University B. Nemcovej, 040 01 Košice, Slovak Republic e-mail: jozef.bucko@tuke.sk

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

Abstract

A graph property is any nonempty isomorphism-closed class of simple (finite or infinite) graphs. A graph property P is of finite character if a graph G has a property P if and only if every finite induced subgraph of G has a property P. Let P₁,P₂,...,P_n be graph properties of finite character, a graph G is said to be (uniquely) (P₁, P₂, …,P_n)-partitionable if there is an (exactly one) partition { V₁, V₂, …, V_n} of V(G) such that G[V_i] ∈ P_i for i = 1,2,...,n. Let us denote by ℜ = P₁ ºP₂ º…ºP_n the class of all (P₁,P₂,...,P_n)-partitionable graphs. A property ℜ = P₁ ºP₂ º…ºP_n, n ≥ 2 is said to be reducible. We prove that any reducible additive graph property ℜ of finite character has a uniquely (P₁, P₂, …,P_n)-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 P_i has a weakly universal graph.

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

2000 Mathematics Subject Classification: 05C15, 05C75.

References

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

Received 31 December 2007
Revised 27 November 2008
Accepted 1 December 2008