A master thesis from Aalborg University
Listefarvninger af planare grafer uden små kredse
Forfatter(e)
Semester
4. semester
Uddannelse
Udgivelsesår
2007
Afleveret
2012-02-14
Abstract
Dette speciale omhandler listefarvninger af grafer. Listefarvninger er farvninger af grafer, hvor farven til hvert punkt skal vælges fra en givet liste af farver. Første halvdel af specialet omhandler acyklisk listefarvning, som er farvninger, hvor ingen kredse i grafen kun har to farver. Vi beskæftiger os med en stadig ubekræftet formodning fra 2002, som siger, at alle planare grafer er acyklisk 5-listefarvbare. I denne del af specialet bevises en række sætninger, som ligner formodningen. I anden halvdel beskæftiger vi os først med Grötzschs sætning, som siger, at enhver planar graf uden trekanter kan farves ved brug af blot tre farver. Det viser sig nemlig, at denne sætning (forholdsvist kort) kan vises vha. et listefarvningsresultat. Bevisstrategien brugt i dette bevis, bruges til at bevise en nedre grænse for antallet af forskellige listefarvninger af grafer med kredse af længde mindst fem.
Kolofon: Denne side er en del af AAU Studenterprojekter — Aalborg Universitets studenterprojektportal. Her kan du finde og downloade offentligt tilgængelige kandidatspecialer og masterprojekter fra hele universitetet fra 2008 og frem. Studenterprojekter fra før 2008 kan findes i trykt form på Aalborg Universitetsbibliotek.
Har du spørgsmål til AAU Studenterprojekter eller Aalborg Universitets forskningsregistrering, formidling og analyse, er du altid velkommen til at kontakte VBN-teamet. Du kan også læse mere i AAU Studenterprojekter FAQ.