Edge colourings of multigraphs [Elektronische Ressource] / von Diego Scheide

Edge Colourings of MultigraphsDissertationzur Erlangung des akademischen Gradesdoctor rerum naturalium (Dr. rer. nat.)vorgelegt der Fakultät für Mathematik und Naturwissenschaftender Technischen Universität Ilmenauvon Dipl.-Math. Diego Scheide1. Gutachter: Prof. Dr. rer. nat. habil. Michael Stiebitz2.hter: Dr. habil. Reinhard Diestel3. Gutachter: Prof. RNDr. Jan KratochvilTag der Einreichung: 21.10.2008Tag der wissenschaftlichen Aussprache: 27.02.2009urn:nbn:de:gbv:ilm1-2009000218Contents1 Introduction 11.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Edge Colourings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Critical Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.4 Elementary Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Edge Colouring Algorithms 72.1 How to Colour a Graph? . . . . . . . . . . . . . . . . . . . . . . . . . 72.2 Implementation Details . . . . . . . . . . . . . . . . . . . . . . . . . 112.3 The Vizing Fan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.4 The Fan Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.5 The Kierstead Path . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302.6 The Tashkinov Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.7 A New Upper Bound for the Chromatic Index . . . . . . . . . . . . . 433 Goldberg’s Conjecture 563.