Aspects of graph homomorphisms and the Hedetniemi Conjecture

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