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.

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.

On considère volontiers que la légende est un objet que se partagent les communautés « extra-modernes ». Traditionnelle, elle est donc lointaine dans le temps et/ou dans l’espace. C’est cette légende qu’étudient, par exemple, les anthropologues. Une autre alternative consiste à penser que la légende est, au contraire, très proche de notre « modernité ». Elle est alors urbaine ou contemporaine, n’est plus vraiment une légende mais une rumeur et s’impose comme le terrain privilégié des « rumorologues ». Traditionnelle, elle se manifeste ainsi dans un ailleurs de la modernité urbaine ; moderne, elle s’y incarne, mais n’est plus traditionnelle. En somme, on refuse à la légende, en tant qu’objet traditionnel, une opérativité socioculturelle à l’intérieur de nos propres sociétés. Or, si les guides les médiatisent, c’est bien qu’elle possède cette opérativité. Toute la question est de savoir comment la définir. À partir d’analyses sémiotiques menées sur un corpus de guides généralistes présentant New York et l’Écosse (Le Routard, les guides Bleu, Vert et Voir, le Lonely Planet, le Petit Futé et la Bibliothèque du voyageur) mais aussi de guides « spécialisés » (Guide du Paris mystérieux, Le Guide de la France mythologique et les Sites mystérieux et légendaires de nos provinces françaises), cette étude qui défend une approche communicationnelle se propose d’aborder le légendaire – à savoir les légendes et la façon dont elles sont commentées par les guides – comme un objet de discours capable d’instituer un certain rapport à la culture qui serait de l’ordre de la curiosité ou de l’insolite. La première partie met ainsi en évidence le fait que le légendaire se manifeste comme un objet anecdotique dans les guides de voyage. Ceux-ci disent, en effet, le caractère extraordinaire du référent légendaire tout en postulant et/ou en instituant, cependant, son insignifiance du point de vue culturel. Anecdotique, le légendaire est, en outre, insaisissable. C’est ce que montre la seconde partie en se concentrant sur la façon dont les guides font des énoncés légendaires des objets proprement inclassables : curieux, ils disent l’étrangeté de l’ordre du monde ; insolites, ils ne disent rien de plus que leur incongruité. S’il est à la fois anecdotique et insaisissable, comment se fait-il que le légendaire fasse pourtant culture ? La troisième partie répond à cette question en montrant que c’est précisément parce qu’il se définit comme tel qu’il fait culture. Ainsi, le légendaire est un objet de discours qui permet, à celui qui le dit, de se manifester dans le monde social à travers une forme d’auctorialité définie par une désinvolture à l’égard des hiérarchies de valeurs traditionnelles. Par ailleurs, elle montre qu’il est un objet de discours qui se livre au lecteur/voyageur dans le but d’être réitéré. Autrement dit, le légendaire circule, à partir de ces dispositifs touristiques que sont les guides, en proposant à ceux qui se l’approprieraient de renverser ou de détourner l’ordre culturel ; d’habiter le monde en tant qu’il est social, le temps infime de l’énonciation légendaire / It is a widespread thought that legends are either traditional or modern, but never both at the same time. When traditional, they are supposed to be told in far away countries, in space and/or in time. These legends are usually studied by anthropologists. When urban, they stop being traditional and are not really legends anymore. They are called “rumours” and are mostly studied by “rumourologists”. However, their presence in travel guides shows that they do have an operativity as traditional objects in our modern culture. Starting with a semiotic analysis of some French-written travel guides conducted through a communicational perspective, this research aims to show that legendary speech – i.e. legends and the way they are told and commented in travel guides – is an object that can institute a specific relationship to culture identified as curiosity or uniqueness (“insolite” in French). The first part of the research enlightens the fact that legendary speech appears as an anecdotal object in travel guides. Indeed, these books suggest that legendary speech does say something extraordinary, but they also seem to believe or want to prove that it is insignificant from a cultural point of view. Anecdotal, legendary speech is also elusive. It is what the second part of the research shows focusing on the way travel guides manage to build up the impossibility to classify this kind of speech. When curious, legendary speech tells us about the strangeness of the world order. When unique, it says no more than its own incongruity. If legendary speech is at the same time anecdotal and elusive, what makes it cultural? The third and last part of the research answers this question. It shows that legendary speech does deal with culture precisely because it appears as both anecdotal and elusive. It is an object of discourse that allows the one who implements it to come out into the social world as an “author”, in the sense that one signs a cultural point of view characterized by a certain casualness towards the common hierarchy of values. It also shows that this speech is delivered to the reader/traveller in order to be reiterated. In other words, the possible circulation of this speech, from travel guides to tourists, suggests that it can be appropriated, so as to reverse or divert the cultural order, so as to inhabit, for the one who says it, the social world, the fractional time of its enunciation