Seminár Ústavu informatiky


Hom-hereditary properties, and hom-properties of finite-character

Moroli D. V. Matsoha
Department of Mathematics and Applied Mathematics, University of Pretoria

29. septembra 2015 (utorok) o 14:00


A graph H is called homomorphic to a graph G if there is an edge preserving map from the vertex set of H to the vertex set of G. A property P ⊆ I, where I is the set of all unlabelled, simple graphs, is hom-hereditary if, for all graphs G ∈ P, P contains all graphs that are homomorphic to G. We will show that the set of all hom-hereditary properties H is a complete and distributive lattice. In addition we will give examples of join and meet-irreducible elements in H, and give a description of some of its elements in terms of minimal forbidden subgraphs.

For all G ∈ I, the set of all graphs in I that are homomorphic to G is referred to as a hom-property, and is denoted by →G. Such a property is of finite-character if whenever it contains all finite in- duced subgraphs of any graph then it contains said graph. Salomaa (1981) proved that, for all finite graphs G, the hom-property →G is of finite-character. We discuss hom-properties of finite character in terms forbidden subgraphs, and we give an example of a graph G with finite chromatic number that induces a hom-property →G that is not of finite character.

 Abstract.pdf (87 kB)