Aspects of graph homomorphisms and the Hedetniemi Conjecture
Loading...
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>