Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl

PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
• # Artykuł - szczegóły

## Discussiones Mathematicae Graph Theory

2016 | 36 | 2 | 479-500

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

EN

### Abstrakty

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

EN

479-500

wydano
2016-05-01
otrzymano
2014-12-15
poprawiono
2015-08-21
zaakceptowano
2015-08-21
online
2016-04-15

### Twórcy

autor
• Department of Mathematics and Applied Mathematics University of Pretoria Pretoria, South Africa
autor
• Department of Mathematics and Applied Mathematics University of Pretoria Pretoria, South Africa
autor
• Emeritus, Department of Mathematical Sciences University of South Africa Pretoria, South Africa