Listefarvninger af planare grafer uden små kredse
Forfattere
Juhl, Line ; Thomsen, Casper
Semester
4. semester
Uddannelse
Udgivelsesår
2007
Abstract
Specialet undersøger listefarvninger i grafteori, hvor hver knude skal farves med en farve fra sin egen liste. Vi forklarer centrale begreber som planar grafer (kan tegnes uden krydsende kanter) og kredse (lukkede stier) og fokuserer først på acyklisk listefarvning, hvor ingen kredse er 2-farvede. Vi behandler en ubekræftet formodning fra 2002 om, at alle planare grafer er acyklisk 5-listefarvbare, og beviser flere sætninger, der ligger tæt på denne påstand. I anden del gennemgår vi Grötzschs sætning, som siger, at enhver planar graf uden trekanter kan farves med tre farver, og viser, hvordan den kan bevises forholdsvist kort via et resultat om listefarvning. Den anvendte bevisstrategi bruges derefter til at etablere en nedre grænse for, hvor mange forskellige listefarvninger grafer med kredse af længde mindst fem kan have.
This thesis studies list colorings in graph theory, where each vertex must be colored using a color from its own list. We clarify key ideas such as planar graphs (drawable without crossing edges) and cycles (closed paths), and first focus on acyclic list coloring, where no cycle is 2-colored. We discuss an open 2002 conjecture stating that all planar graphs are acyclically 5-list-colorable, and prove several theorems that closely relate to this claim. In the second part, we revisit Grötzsch’s theorem, which says that every triangle-free planar graph is 3-colorable, and show that it admits a relatively short proof via a list-coloring result. We then use the same proof strategy to establish a lower bound on the number of distinct list colorings for graphs whose cycles have length at least five.
[Dette resumé er genereret ved hjælp af AI]