Philosophiae Doctor - PhD / The history of the pursuit of uncolourable cubic graphs dates back more than a century.
This pursuit has evolved from the slow discovery of individual uncolourable
cubic graphs such as the famous Petersen graph and the Blanusa snarks, to discovering
in nite classes of uncolourable cubic graphs such as the Louphekine and
Goldberg snarks, to investigating parameters which measure the uncolourability of
cubic graphs. These parameters include resistance, oddness and weak oddness,
ow
resistance, among others. In this thesis, we consider current ideas and problems regarding
the uncolourability of cubic graphs, centering around these parameters. We
introduce new ideas regarding the structural complexity of these graphs in question.
In particular, we consider their 3-critical subgraphs, speci cally in relation to resistance.
We further introduce new parameters which measure the uncolourability of
cubic graphs, speci cally relating to their 3-critical subgraphs and various types of
cubic graph reductions. This is also done with a view to identifying further problems
of interest. This thesis also presents solutions and partial solutions to long-standing
open conjectures relating in particular to oddness, weak oddness and resistance.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:uwc/oai:etd.uwc.ac.za:11394/7869 |
| Date | January 2020 |
| Creators | Allie, Imran |
| Contributors | Mwambene, Eric, Steffen, Eckhard |
| Publisher | University of the Western Cape |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Rights | University of the Western Cape |
Page generated in 0.0016 seconds