Edge Colourings, Strong Edge Colourings, and Matchings in Graphs

Student thesis: Master thesis (including HD thesis)

  • Frederik Vestergaard Kjemtrup
4. term, Mathematics, Master (Master Programme)
This master's thesis deals with graph theory, specifically the theory of edge colourings, strong edge colourings, matchings, and factorisations of graphs.
After a brief introduction to edge-colouring terminology, Chapter 2 contains a proof of Vizing's theorem, bounding the chromatic index of graphs in a general way.
Chapter 3 considers edge colouring graphs from a different perspective, that of matchings. Matchings are shown to be inherently linked to factors of graphs, whereupon several results on both matchings and factors are proven throughout the chapter.
In Chapter 4, a special case of edge colouring is considered, namely that of strong edge colourings.
It is shown that a well-known conjecture about an upper bound on the strong chromatic index would be sharp if the conjecture were true. Then, a special case of the conjecture is proven for bipartite graphs.
Finally, Chapter 5 contains a proof of a theorem which confirms the conjectured upper bound on the strong chromatic index, however only in the special case of cubic graphs.
Publication date26 May 2017
Number of pages57
ID: 258315661