The Quest for A Characterization of Hom-Properties of Finite Character

Izak Broere; Moroli D.V. Matsoha; Johannes Heidema

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 2, page 479-500
  • ISSN: 2083-5892

Abstract

top
A graph property is a set of (countable) graphs. A homomorphism from a graph G to a graph H is an edge-preserving map from the vertex set of G into the vertex set of H; if such a map exists, we write G → H. Given any graph H, the hom-property →H is the set of H-colourable graphs, i.e., the set of all graphs G satisfying G → H. A graph property P is of finite character if, whenever we have that F ∈ P for every finite induced subgraph F of a graph G, then we have that G ∈ P too. We explore some of the relationships of the property attribute of being of finite character to other property attributes such as being finitely-induced-hereditary, being finitely determined, and being axiomatizable. We study the hom-properties of finite character, and prove some necessary and some sufficient conditions on H for →H to be of finite character. A notable (but known) sufficient condition is that H is a finite graph, and our new model-theoretic proof of this compactness result extends from hom-properties to all axiomatizable properties. In our quest to find an intrinsic characterization of those H for which →H is of finite character, we find an example of an infinite connected graph with no finite core and chromatic number 3 but with hom-property not of finite character.

How to cite

top

Izak Broere, Moroli D.V. Matsoha, and Johannes Heidema. "The Quest for A Characterization of Hom-Properties of Finite Character." Discussiones Mathematicae Graph Theory 36.2 (2016): 479-500. <http://eudml.org/doc/277119>.

@article{IzakBroere2016,
abstract = {A graph property is a set of (countable) graphs. A homomorphism from a graph G to a graph H is an edge-preserving map from the vertex set of G into the vertex set of H; if such a map exists, we write G → H. Given any graph H, the hom-property →H is the set of H-colourable graphs, i.e., the set of all graphs G satisfying G → H. A graph property P is of finite character if, whenever we have that F ∈ P for every finite induced subgraph F of a graph G, then we have that G ∈ P too. We explore some of the relationships of the property attribute of being of finite character to other property attributes such as being finitely-induced-hereditary, being finitely determined, and being axiomatizable. We study the hom-properties of finite character, and prove some necessary and some sufficient conditions on H for →H to be of finite character. A notable (but known) sufficient condition is that H is a finite graph, and our new model-theoretic proof of this compactness result extends from hom-properties to all axiomatizable properties. In our quest to find an intrinsic characterization of those H for which →H is of finite character, we find an example of an infinite connected graph with no finite core and chromatic number 3 but with hom-property not of finite character.},
author = {Izak Broere, Moroli D.V. Matsoha, Johannes Heidema},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {(countable) graph; homomorphism (of graphs); property of graphs; hom-property; (finitely-)induced-hereditary property; finitely determined property; (weakly) finite character; axiomatizable property; compactness theorems; core; connectedness; chromatic number; clique number; independence number; dominating set; countable graph; homomorphism; finitely-induced hereditary property; weakly finite character},
language = {eng},
number = {2},
pages = {479-500},
title = {The Quest for A Characterization of Hom-Properties of Finite Character},
url = {http://eudml.org/doc/277119},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Izak Broere
AU - Moroli D.V. Matsoha
AU - Johannes Heidema
TI - The Quest for A Characterization of Hom-Properties of Finite Character
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 2
SP - 479
EP - 500
AB - A graph property is a set of (countable) graphs. A homomorphism from a graph G to a graph H is an edge-preserving map from the vertex set of G into the vertex set of H; if such a map exists, we write G → H. Given any graph H, the hom-property →H is the set of H-colourable graphs, i.e., the set of all graphs G satisfying G → H. A graph property P is of finite character if, whenever we have that F ∈ P for every finite induced subgraph F of a graph G, then we have that G ∈ P too. We explore some of the relationships of the property attribute of being of finite character to other property attributes such as being finitely-induced-hereditary, being finitely determined, and being axiomatizable. We study the hom-properties of finite character, and prove some necessary and some sufficient conditions on H for →H to be of finite character. A notable (but known) sufficient condition is that H is a finite graph, and our new model-theoretic proof of this compactness result extends from hom-properties to all axiomatizable properties. In our quest to find an intrinsic characterization of those H for which →H is of finite character, we find an example of an infinite connected graph with no finite core and chromatic number 3 but with hom-property not of finite character.
LA - eng
KW - (countable) graph; homomorphism (of graphs); property of graphs; hom-property; (finitely-)induced-hereditary property; finitely determined property; (weakly) finite character; axiomatizable property; compactness theorems; core; connectedness; chromatic number; clique number; independence number; dominating set; countable graph; homomorphism; finitely-induced hereditary property; weakly finite character
UR - http://eudml.org/doc/277119
ER -

References

top
  1. [1] B.L. Bauslaugh, Core-like properties of infinite graphs and structures, Discrete Math. 138 (1995) 101-111. doi:10.1016/0012-365X(94)00191-K[Crossref] 
  2. [2] B.L. Bauslaugh, Cores and compactness of infinite directed graphs, J. Combin. Theory Ser. B 68 (1996) 255-276. Zbl0861.05028
  3. [3] B.L. Bauslaugh, List-Compactness of directed graphs, Graphs Combin. 17 (2001) 17-38. doi:10.1007/s003730170052[Crossref] Zbl0990.05061
  4. [4] M. Borowiecki, I. Broere, M. Frick, G. Semanišin and P. Mihók, A survey of hered- itary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50. doi:10.7151/dmgt.1037[Crossref] Zbl0902.05026
  5. [5] J. Bucko and P. Mihók, On infinite uniquely partitionable graphs and graph proper- ties of finite character , Discuss. Math. Graph Theory 29 (2009) 241-251. doi:10.7151/dmgt.1444[Crossref] Zbl1194.05037
  6. [6] G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs, Fifth Edition (CRC Press, Boca Raton, 2011). Zbl1211.05001
  7. [7] R. Cowen, S.H. Hechler and P. Mihók, Graph coloring compactness theorems, Sci. Math. Jpn. 56 (2002) 171-180. Zbl1023.05048
  8. [8] B.A. Davey and H.A. Priestly, Introduction to Lattices and Order, Second Edition (Cambridge University Press, New York, 2008). 
  9. [9] N.G. de Bruijn and P. Erdős, A colour problem for infinite graphs and a problem in the theory of relations, Indag. Math. 13 (1951) 371-373. doi:10.1016/S1385-7258(51)50053-7[Crossref] Zbl0044.38203
  10. [10] R. Diestel, Graph Theory, Fourth Edition (Graduate Texts in Mathematics 173, Springer, Heidelberg, 2010). doi:10.1007/978-3-642-14279-6[Crossref] 
  11. [11] J.H. Hattingh, Relatiewe semantiese afleibaarheid [Relative semantical entailment] (Master’s dissertation (in Afrikaans), Rand Afrikaans University, Johannesburg, 1985). 
  12. [12] T.W. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., New York, 1998). Zbl0890.05002
  13. [13] P. Hell and J. Nešetřil, Graphs and Homomorphisms (Oxford University Press, Oxford, 2004). 
  14. [14] W. Hodges, First-order Model Theory (The Stanford Encyclopedia of Philosophy (Summer 2009 Edition), E.N. Zalta (Ed.), 2009). http://plato.stanford.edu/archives/sum2009/entries/modeltheory-fol 
  15. [15] R. Kellerman, private communication. 
  16. [16] A. Robinson, Introduction to Model Theory and to the Metamathematics of Algebra (North-Holland, Amsterdam, 1963). Zbl0118.25302
  17. [17] A. Salomaa, On color-families of graphs, Ann. Acad. Sci. Fenn. Math. 6 (1981) 135-148. doi:10.5186/aasfm.1981.0619[Crossref] Zbl0497.05027
  18. [18] E. Welzl, Color-families are dense, Theoret. Comput. Sci. 17 (1982) 29-41. doi:10.1016/0304-3975(82)90129-3[Crossref] Zbl0482.68063

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.