On infinite uniquely partitionable graphs and graph properties of finite character

Jozef Bucko; Peter Mihók

Discussiones Mathematicae Graph Theory (2009)

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

Abstract

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

How to cite

top

Jozef 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. [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. [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. [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. [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. [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. [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. [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. [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. [9] R.L. Graham, M. Grotschel and L. Lovasz, Handbook of Combinatorics (Elsevier Science B.V., Amsterdam, 1995). Zbl0833.05001
  10. [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. [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. [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. [13] P. Mihók, Unique factorization theorem, Discuss. Math. Graph Theory 20 (2000) 143-154, doi: 10.7151/dmgt.1114. Zbl0968.05032
  14. [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. [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. [16] N.W. Sauer, Canonical vertex partitions, Combinatorics, Probability and Computing 12 (2003) 671-704, doi: 10.1017/S0963548303005765. Zbl1062.03046
  17. [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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.