Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: hom-property

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

On universal graphs for hom-properties

100%

Mihók P., Miškuf J., Semanišin G.

Discussiones Mathematicae Graph Theory

2009

tom 29

nr 2

401-409

A graph property is any isomorphism closed class of simple graphs. For a simple finite graph H, let → H denote the class of all simple countable graphs that admit homomorphisms to H, such classes of graphs are called hom-properties. Given a graph property 𝓟, a graph G ∈ 𝓟 is universal in 𝓟 if each member of 𝓟 is isomorphic to an induced subgraph of G. In particular, we consider universal graphs in → H and we give a new proof of the existence of a universal graph in → H, for any finite graph H.

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

51%

Broere I., Matsoha M. D. V., Heidema J.

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 2

479-500

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.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Broere I.

1 Heidema J.

1 Matsoha M. D. V.

1 Mihók P.

1 Miškuf J.

1 Semanišin G.

1 2016

1 2009

Wyniki wyszukiwania

On universal graphs for hom-properties

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