Listefarvninger af planare grafer uden små kredse

Studenteropgave: Speciale (inkl. HD afgangsprojekt)

  • Line Juhl
  • Casper Thomsen
4. semester, Matematik, Kandidat (Kandidatuddannelse)
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.
SprogDansk
Udgivelsesdatojun. 2007
ID: 61070641