Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Aspects of graph homomorphisms and the Hedetniemi Conjecture
Thesis (PhD)--University of Pretoria, 2015.
Saved in:
| Other Authors: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
University of Pretoria
2016
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613695263113216 |
|---|---|
| access_status_str | Open Access |
| author2 | Broere, Izak |
| author_browse | Broere, Izak |
| author_facet | Broere, Izak |
| collection | Thesis |
| dc_rights_str_mv | © 2016, University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria. |
| description | Thesis (PhD)--University of Pretoria, 2015. |
| format | Thesis |
| id | oai:repository.up.ac.za:2263/53525 |
| institution | University of Pretoria (South Africa) |
| language | English |
| last_indexed | 2026-06-10T12:40:13.972Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UPSpace — University of Pretoria Institutional Repository |
| publishDate | 2016 |
| publishDateRange | 2016 |
| publishDateSort | 2016 |
| publisher | University of Pretoria |
| publisherStr | University of Pretoria |
| record_format | dspace |
| source_str | UPSpace — University of Pretoria Institutional Repository |
| spelling | oai:repository.up.ac.za:2263/53525 Aspects of graph homomorphisms and the Hedetniemi Conjecture Broere, Izak moroli.matsoha@up.ac.za Matsoha, Moroli David Vusi UCTD Thesis (PhD)--University of Pretoria, 2015. 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 Mathematics and Applied Mathematics PhD Unrestricted 2016-07-01T10:33:18Z 2016-07-01T10:33:18Z 2016-04-13 2015 Thesis 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> A2016 http://hdl.handle.net/2263/53525 en © 2016, University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria. application/pdf University of Pretoria |
| spellingShingle | UCTD Aspects of graph homomorphisms and the Hedetniemi Conjecture |
| title | Aspects of graph homomorphisms and the Hedetniemi Conjecture |
| title_full | Aspects of graph homomorphisms and the Hedetniemi Conjecture |
| title_fullStr | Aspects of graph homomorphisms and the Hedetniemi Conjecture |
| title_full_unstemmed | Aspects of graph homomorphisms and the Hedetniemi Conjecture |
| title_short | Aspects of graph homomorphisms and the Hedetniemi Conjecture |
| title_sort | aspects of graph homomorphisms and the hedetniemi conjecture |
| topic | UCTD |
| url | http://hdl.handle.net/2263/53525 |