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.

The work in this thesis can be divided into two different parts. In the first part, we suggest an approximate edge 3-coloring polynomial time algorithm for cubic graphs. For any cubic graph with n vertices, using this coloring algorithm, we get an edge 3-coloring with at most n/3 error vertices. In the second part, we study Jim Propp's Rotor-Router model on some non-bipartite graph. We find the difference between the number of chips at vertices after performing a walk on this graph using Propp model and the expected number of chips after a random walk. It is known that for line of integers and d-dimenional grid, this deviation is constant. However, it is also proved that for k-ary infinite trees, for some initial configuration the deviation is no longer a constant and say it is D. We present a similar study on some non-bipartite graph constructed from k-ary infinite trees and conclude that for this graph with the same initial configuration, the deviation is almost (k²)D.

Suppose a group G can be generated by two subgroups, P1 and P2, both isomorphic to S4 which have intersection isomorphic to D8- the dihedral group of order 8. Then G is known as a faithful completion of the Goldschmidt G3-amalgam. In this thesis we consider the alternating groups as faithful completions of the Goldschmidt G3-amalgam.

Berge and Fulkerson conjectured that for each cubic bridgeless graph there are six perfect matchings such that each edge is contained in exactly two of them. Another conjecture due to Berge says that we can cover cubic bridgeless graphs by five perfect matchings. Both conjectures are studied for over forty years. Abreu et al. [2016] introduce a new class of graphs (called treelike snarks) which cannot be covered by less then five perfect matchings. We show that their lower bound on number of perfect matchings is tight. Moreover we prove that a bigger class of cubic bridgeless graphs admits Berge conjecture. Finally, we also show that Berge-Fulkerson conjecture holds for treelike snarks.

For a number of unsolved problems in graph theory such as the cycle double cover conjecture, Fulkerson's conjecture and Tutte's 5-flow conjecture it is sufficient to prove them for a family of graphs called snarks. Named after the mysterious creature in Lewis Carroll's poem, a \emph{snark} is a cyclically 4-edge connected 3-regular graph of girth at least 5 which cannot be properly edge coloured using three colours. Snarks and problems for which an edge minimal counterexample must be a snark are the central topics of this thesis.   The first part of this thesis is intended as a short introduction to the area. The second part is an introduction to the appended papers and the third part consists of the four papers presented in a chronological order. In Paper I we study the strong cycle double cover conjecture and stable cycles for small snarks. We prove that if a bridgeless cubic graph $G$ has a cycle of length at least $|V(G)|-9$ then it also has a cycle double cover. Furthermore we show that there exist cyclically 5-edge connected snarks with stable cycles and that there exists an infinite family of snarks with stable cycles of length 24. In Paper II we present a new algorithm for generating all non-isomorphic snarks with a given number of vertices. We generate all snarks on 36 vertices and less and study these with respect to various properties. We find that a number of conjectures on cycle covers and colourings holds for all graphs of these orders. Furthermore we present counterexamples to no less than eight published conjectures on cycle coverings, cycle decompositions and the general structure of regular graphs.     In Paper III we show that Jaeger's Petersen colouring conjecture holds for three infinite families of snarks and that a minimum counterexample to this conjecture cannot contain a certain subdivision of $K_{3,3}$ as a subgraph. Furthermore, it is shown that one infinite family of snarks have strong Petersen colourings while another does not have any such colourings. Two simple constructions for snarks with arbitrary high oddness and resistance is given in Paper IV. It is observed that some snarks obtained from this construction have the property that they require at least five perfect matchings to cover the edges. This disproves a suggested strengthening of Fulkerson's conjecture.

Given a complete graph K_n = (V,E) with non-negative edge costs c ∈ R^E, the problem multi-2EC_cost is that of finding a 2-edge connected spanning multi-subgraph of K_n with minimum cost. It is believed that there are no efficient ways to solve the problem exactly, as it is NP-hard. Methods such as approximation algorithms, which rely on lower bounds like the linear programming relaxation multi-2EC^LP of multi-2EC , thus become vital cost cost to obtain solutions guaranteed to be close to the optimal in a fast manner. In this thesis, we focus on the integrality gap αmulti-2EC of multi-2EC^LP , which is a measure of the quality of multi-2EC^LP as a lower bound. Although we currently only know cost that 6/5 ≤ αmulti-2EC_cost ≤ 3 , the integrality gap for multi-2EC_cost has been conjectured to be 6/5. We explore the idea of using the structure of solutions for αmulti-2EC_cost and the concept of convex combination to obtain improved bounds for αmulti-2EC_cost. We focus our efforts on a family J of half-integer solutions that appear to give the largest integrality gap for multi-2EC_cost. We successfully show that the conjecture αmulti-2EC_cost = 6/5 is true for any cost functions optimized by some x∗ ∈ J. We also study the related problem 2EC_size, which consists of finding the minimum size 2-edge connected spanning subgraph of a 2-edge connected graph. The problem is NP-hard even at its simplest, when restricted to cubic 3-edge connected graphs. We study that case in the hope of finding a more general method, and we show that every 3-edge connected cubic graph G = (V ′, E′), with n = |V ′| allows a 2EC_size solution for G of size at most 7n/6 This improves upon Boyd, Iwata and Takazawa’s guarantee of 6n/5 and extend Takazawa’s 7n/6 guarantee for bipartite cubic 3-edge connected graphs to all cubic 3-edge connected graphs.