Aspects of graph homomorphisms and the Hedetniemi Conjecture

Loading...
Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

University of Pretoria

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

Description

Thesis (PhD)--University of Pretoria, 2015.

Keywords

UCTD

Sustainable Development Goals

Citation

Matsoha, MDV 2016, Aspects of graph homomorphisms and the Hedetniemi Conjecture, PhD Thesis, University of Pretoria, Pretoria, viewed yymmdd <http://hdl.handle.net/2263/53525>