# 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

## Access Full Article

top## Abstract

top## How to cite

topIzak 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] 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] B.L. Bauslaugh, Cores and compactness of infinite directed graphs, J. Combin. Theory Ser. B 68 (1996) 255-276. Zbl0861.05028
- [3] B.L. Bauslaugh, List-Compactness of directed graphs, Graphs Combin. 17 (2001) 17-38. doi:10.1007/s003730170052[Crossref] Zbl0990.05061
- [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] 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] G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs, Fifth Edition (CRC Press, Boca Raton, 2011). Zbl1211.05001
- [7] R. Cowen, S.H. Hechler and P. Mihók, Graph coloring compactness theorems, Sci. Math. Jpn. 56 (2002) 171-180. Zbl1023.05048
- [8] B.A. Davey and H.A. Priestly, Introduction to Lattices and Order, Second Edition (Cambridge University Press, New York, 2008).
- [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] R. Diestel, Graph Theory, Fourth Edition (Graduate Texts in Mathematics 173, Springer, Heidelberg, 2010). doi:10.1007/978-3-642-14279-6[Crossref]
- [11] J.H. Hattingh, Relatiewe semantiese afleibaarheid [Relative semantical entailment] (Master’s dissertation (in Afrikaans), Rand Afrikaans University, Johannesburg, 1985).
- [12] T.W. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., New York, 1998). Zbl0890.05002
- [13] P. Hell and J. Nešetřil, Graphs and Homomorphisms (Oxford University Press, Oxford, 2004).
- [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] R. Kellerman, private communication.
- [16] A. Robinson, Introduction to Model Theory and to the Metamathematics of Algebra (North-Holland, Amsterdam, 1963). Zbl0118.25302
- [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] 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 ?

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