Edge Colourings, Strong Edge Colourings, and Matchings in Graphs

Kjemtrup, Frederik Vestergaard

4. term

Mathematics, Master

2017

2017-05-25

57 pages

Dette kandidatprojekt i matematik beskæftiger sig med grafteori, specifikt teorien vedrørende kantfarvninger, stærke kantfarvninger og parringer samt faktoriseringer af grafer. Kantfarvning af en graf består i at tildele hver kant en farve, sådan at intet par af tilstødende kanter tildeles samme farve. Selvfølgelig kan dette opnås ved at tildele en særskilt farve til hver kant i en given graf, men ofte kan man have interesse i at benytte så få farver som muligt. Efter en kort introduktion til kantfarvningsterminologi, indeholder Kapitel 2 et bevis for Vizings sætning, som angiver en generel øvre grænse for grafers kromatiske indeks, som er det mindste antal farver, der behøves for at opnå en gyldig farvning af alle grafens kanter. Herefter betragtes i Kapitel 3 kantfarvninger fra et andet perspektiv, nemlig parringer. Parringer vises at være grundlæggende forbundet med faktorer i grafer, hvorefter flere resultater vedrørende parringer og faktorer bevises. Dernæst skærpes begrebet kantfarvninger i Kapitel 4 til det specialtilfælde, som stærke kantfarvninger udgør. En kantfarvning af en graf kaldes stærk, hvis der om enhver kant i grafen gælder, at alle dennes tilstødende kanter er tildelt særskilte farver. Det bevises, at en velkendt formodning om en øvre grænse for det stærke kromatiske indeks vil være skarp, såfremt formodningen viser sig at være sand. Denne formodning går i grove træk ud på, at en graf med højeste grad $\Delta$ højst kan have stærkt kromatisk indeks $\frac{5}{4}\Delta^2$. Dernæst bekræftes et særtilfælde af formodningen som kun betragter særlige todelte grafer. Resultatet lyder, at for en todelt graf, hvori den ene delgraf har højeste grad $2$, vil det stærke kromatiske indeks højst være lig det dobbelte af grafens højeste grad. Endelig indeholder Kapitel 5 et bevis for en sætning, som for kubiske grafer bekræfter den omtalte formodning om en øvre grænse for det stærke kromatiske indeks.

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.

grafteori ; kantfarvning ; stærk kantfarvning ; parring ; faktorer ; faktorisering

Download
View record in AAU Student Projects