# On infinite uniquely partitionable graphs and graph properties of finite character

Discussiones Mathematicae Graph Theory (2009)

- Volume: 29, Issue: 2, page 241-251
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJozef Bucko, and Peter Mihók. "On infinite uniquely partitionable graphs and graph properties of finite character." Discussiones Mathematicae Graph Theory 29.2 (2009): 241-251. <http://eudml.org/doc/270677>.

@article{JozefBucko2009,

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[V_i] ∈ _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.},

author = {Jozef Bucko, Peter Mihók},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {graph property of finite character; reducibility; uniquely partitionable graphs; weakly universal graph},

language = {eng},

number = {2},

pages = {241-251},

title = {On infinite uniquely partitionable graphs and graph properties of finite character},

url = {http://eudml.org/doc/270677},

volume = {29},

year = {2009},

}

TY - JOUR

AU - Jozef Bucko

AU - Peter Mihók

TI - On infinite uniquely partitionable graphs and graph properties of finite character

JO - Discussiones Mathematicae Graph Theory

PY - 2009

VL - 29

IS - 2

SP - 241

EP - 251

AB - 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[V_i] ∈ _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.

LA - eng

KW - graph property of finite character; reducibility; uniquely partitionable graphs; weakly universal graph

UR - http://eudml.org/doc/270677

ER -

## References

top- [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. Zbl0902.05026
- [2] I. Broere and J. Bucko, Divisibility in additive hereditary graph properties and uniquely partitionable graphs, Tatra Mt. Math. Publ. 18 (1999) 79-87. Zbl0951.05034
- [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. Zbl1013.05066
- [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. Zbl0906.05057
- [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. Zbl0928.03049
- [6] R. Cowen, S.H. Hechler and P. Mihók, Graph coloring compactness theorems equivalent to BPI, Scientia Math. Japonicae 56 (2002) 171-180. Zbl1023.05048
- [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. Zbl1067.05057
- [8] B. Ganter and R. Wille, Formal Concept Analysis - Mathematical Foundation (Springer-Verlag Berlin Heidelberg, 1999), doi: 10.1007/978-3-642-59830-2. Zbl0909.06001
- [9] R.L. Graham, M. Grotschel and L. Lovasz, Handbook of Combinatorics (Elsevier Science B.V., Amsterdam, 1995). Zbl0833.05001
- [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. Zbl0175.50205
- [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. Zbl1056.05062
- [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. Zbl0623.05043
- [13] P. Mihók, Unique factorization theorem, Discuss. Math. Graph Theory 20 (2000) 143-154, doi: 10.7151/dmgt.1114. Zbl0968.05032
- [14] P. Mihók, On the lattice of additive hereditary properties of object systems, Tatra Mt. Math. Publ. 30 (2005) 155-161. Zbl1150.05394
- [15] P. Mihók and G. Semanišin, Unique Factorization Theorem and Formal Concept Analysis, CLA 2006, Yasmin, Hammamet, Tunisia, (2006), 195-203. Zbl1133.05306
- [16] N.W. Sauer, Canonical vertex partitions, Combinatorics, Probability and Computing 12 (2003) 671-704, doi: 10.1017/S0963548303005765. Zbl1062.03046
- [17] E.R. Scheinerman, On the structure of hereditary classes of graphs, J. Graph Theory 10 (1986) 545-551, doi: 10.1002/jgt.3190100414. Zbl0609.05057

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.