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

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 -