The quest for a characterization of hom-properties of finite character

Show simple item record Broere, Izak Matsoha, Moroli D.V. Heiema, Johannes 2016-08-01T05:50:47Z 2016-08-01T05:50:47Z 2016
dc.description.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. en_ZA
dc.description.department Mathematics and Applied Mathematics en_ZA
dc.description.librarian am2016 en_ZA
dc.description.sponsorship National Research Foundation of South Africa (Grant Number 90841) en_ZA
dc.description.uri en_ZA
dc.identifier.citation Broere, I, Matsoha, MDV & Heidema, J 2016, 'The quest for a characterization of hom-properties of finite character', Discussiones Mathematicae Graph Theory, vol. 36, pp. 479-500. en_ZA
dc.identifier.issn 1234-3099 (print)
dc.identifier.issn 2083-5892 (online)
dc.identifier.other 10.7151/dmgt.1873
dc.language.iso en en_ZA
dc.publisher De Gruyter Open en_ZA
dc.rights © Authors. This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License. en_ZA
dc.subject (Countable) graph en_ZA
dc.subject Homomorphism (of graphs) en_ZA
dc.subject Property of graphs en_ZA
dc.subject Hom-property en_ZA
dc.subject (Finitely-)induced-hereditary property en_ZA
dc.subject Finitely determined property en_ZA
dc.subject (Weakly) finite character en_ZA
dc.subject Axiomatizable property en_ZA
dc.subject Compactness theorems en_ZA
dc.subject Core en_ZA
dc.subject Connectedness en_ZA
dc.subject Chromatic number en_ZA
dc.subject Clique number en_ZA
dc.subject Independence number en_ZA
dc.subject Dominating set en_ZA
dc.title The quest for a characterization of hom-properties of finite character en_ZA
dc.type Article en_ZA

Files in this item

This item appears in the following Collection(s)

Show simple item record