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.
