Abstract:
The Compactness Theorem for graph colourings, by De Bruijn
and Erd}os, can be restated as follows. If all the nite subgraphs of
a graph G are homomorphic to a nite complete graph Kn, then G
is also homomorphic to Kn. In short, nite complete graphs have
the following interesting quality: a graph G is not homomorphic to a
complete graph if and only if some nite subgraph of G is not homo-
morphic to said complete graph. There have been many investigations
into graphs H that posses this remarkable characteristic of complete
graphs. We further this investigation and describe a graph with nite
chromatic number that does not posses the aforementioned quality.
Our approach is from a lattice theoretic stand point. That is to say
we will study those sets of graphs that are homomorphic to a speci c
graph. Such sets we call hom-properties, and when a graph possesses the aforementioned characteristic we will say that it induces or gener-
ates a hom-property of nite character. We also study those properties
(sets of graphs) that are composed from the union of hom-properties.
We do this to gain more insight into the existence of a homomorphism
from one graph to another.
Continuing with this study of homomorphisms we describe a tech-
nique of constructing, for selected graphs G and H bearing the same
chromatic number, a graph F that has the same chromatic number
and is homomorphic to both G and H. We then apply this tech-
nique to solving some special cases of Hedetniemi's Conjecture. The
results obtained from this approach extend the results obtained by
Burr, Erd}os and Lov asz, and broaden a result that was obtained by
Du us, Sands and Woodrow, and also by Welzl.
iii
