Project topics and materials
Get Complete Project Material File(s) Now! »
Hom-properties of nite character
The graphs dealt with in this chapter are countable unlabelled simple graphs. By `simple’ we mean loop-less, undirected graphs without parallel edges. In addition we make no distinction between isomorphic graphs. Although we are dealing with unlabelled graphs we will on occasion assign labels to their vertices. This we will do only better to describe the vertex set and edge set of the graph in question. We denote the set of all such graphs by I. By a property we will mean any subset P of I.
We mainly study properties (subsets of I) that contain graphs that are all homomorphic to a specied graph H. Such properties we will call homproperties induced or generated by H. This chapter, in some way or another, revolves around these properties. We are interested in whether the existence of a homomorphism from a graph G to a graph H is guaranteed by the existence of a homomorphism from each nite subgraph of G to the graph H. To be more precise we are interested in those graphs H which satisfy the following. Whenever a graph G is such that there exist homomorphisms from each of its nite subgraphs to H then there exists a homomorphism from G to H. When given such a graph H we say that the set of all graphs for which there exists a homomorphism into H, that is the hom-property induced by H, is of nite character. We will give some necessary and sucient conditions for a hom-property induced by a graph H to be of nite character. We shall also give an example of a countable graph with nite chromatic number that does not posses this previously mentioned quality. This concept of nite character relates very closely to the Compactness Theorem for graph colourings by De Bruijn and Erd}os. We shall in addition mention some related results from other authors.
As an introduction the rst two sections are concerned with graph ho momorphisms and hom-properties. This is followed by a discussion on homproperties of nite character, and then lastly, we take a look at those properties that are unions of hom-properties. For these properties we will describe the lattice they induce and discuss some of the meet and join-irreducible elements in this lattice.
1 Preliminaries
1.1 Graph theoretic denitions and notation
1.2 Lattice theoretic denitions and notation .
1.3 Summary
2 Hom-properties of nite character
2.1 Introduction .
2.2 Homomorphisms
2.3 Hom-properties .
2.4 Hom-properties of nite character
2.4.1 Necessary and sucient conditions for a hom-property to be of nite-character .
2.4.2 A hom-property that is not of nite character
2.5 Hom-hereditary properties
3 Results on the Hedetniemi Conjecture
3.1 Introduction
3.2 The Hajos-type construct
3.3 An improvement of the Burr, Erd}os and Lovasz Theorem
3.4 The generalized Mycielski construct
3.5 The Hajos-Pe-string construct
3.6 An extension on the Duus, Sands and Woodrow Theorem .
3.7 Hom-properties and the Hedetniemi Conjecture .
References
