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

• Volume: 36, Issue: 2, page 479-500
• ISSN: 2083-5892

top

Abstract

top
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.

How to cite

top

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 -

NotesEmbed?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.