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

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

Discussiones Mathematicae Graph Theory (2016)

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

## Access Full Article

top## Abstract

top## How to cite

topIzak 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 ?

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