Edge Colourings, Strong Edge Colourings, and Matchings in Graphs
Author
Kjemtrup, Frederik Vestergaard
Term
4. term
Education
Publication year
2017
Submitted on
2017-05-26
Pages
57
Abstract
Denne specialeafhandling undersøger, hvordan man farver kanter i grafer for at undgå konflikter. Efter en kort introduktion til centrale begreber i kantfarvning beviser afhandlingen en generel grænse for det kromatiske indeks (Vizings sætning), som angiver det mindste antal farver, der kræves for en gyldig kantfarvning. Derefter betragtes kantfarvning ud fra matchinger (mængder af kanter uden fælles endepunkter) og vises, hvordan matchinger er tæt knyttet til faktorer i grafer (delgrafer, der omfatter alle knuder og opfylder bestemte gradkrav), med flere resultater om begge dele. Dernæst behandles stærk kantfarvning, hvor selv kanter, der ligger tæt på hinanden (adjacente eller forbundet gennem en fælles nabo), skal have forskellige farver. Her diskuteres en velkendt formodning om en øvre grænse for det stærke kromatiske indeks, og det vises, at grænsen ville være skarp, hvis formodningen er sand. Afhandlingen beviser også formodningen i en særlig tilfælde for to-delte grafer og afslutter med at bekræfte den formodede øvre grænse i den særlige tilfælde af kubiske grafer (grafer hvor hver knude har grad tre).
This thesis explores how to color the edges of graphs to avoid conflicts. After introducing key terms in edge coloring, it proves a general bound on the chromatic index (Vizing’s theorem), the minimum number of colors needed for a proper edge coloring. It then views edge coloring through matchings (sets of edges with no shared endpoints) and shows how matchings relate to factors of graphs (subgraphs that include all vertices and meet degree conditions), establishing several results about both. Next, it studies strong edge colorings, where even nearby edges (adjacent or linked through a shared neighbor) must have different colors, and discusses a well-known conjecture that gives an upper bound on the strong chromatic index. The thesis shows this bound would be tight if the conjecture holds, proves the conjecture in a special case for bipartite graphs, and finally confirms the conjectured upper bound in the special case of cubic graphs (graphs where every vertex has degree three).
[This abstract was generated with the help of AI]
Keywords
Documents