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.