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

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

Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 479-500

Résumé

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 mathcalP is of finite character if, whenever we have that F ∈𝒫 for every finite induced subgraph F of a graph G, then we have that G ∈𝒫 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.

Détail

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