PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 2 | 479-500
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
Języki publikacji
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.
Wydawca
Rocznik
Tom
36
Numer
2
Strony
479-500
Opis fizyczny
Daty
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, izak.broere@up.ac.za
  • Department of Mathematics and Applied Mathematics University of Pretoria Pretoria, South Africa, moroli.matsoha@up.ac.za
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1873
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.