Aftales med underviser, Eksamenstidspunktet
aftales med de studerende
Evalueringsform:
Eksamens varighed:
Bedømmelsesform:
Obligatoriske forudsætninger:
Anbefalede forudsætninger:
Deltagerbegrænsning:
Minimum 6 Maksimum: 100
Overordnede kursusmål:
Kurset vil indeholde en række klassiske grafteoretiske resultater,
såsom sætningerne af Tutte, Ramsey, Turan, Kuratowski,
Brooks, Dirac, Smith, og Vizing, samt Jordan's kurvesætning.
Desuden vil mere moderne problemstillinger, såsom liste-farvninger,
blive gennemgået.
Læringsmål:
En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:
Anvende frembringerfunktioner
Anvende tælleteknik, illustreret med Ramsey's sætning
Anvende grundlaget for plane grafer: Jordan's
kurvesætning
Anvende Kuratowski 's planaritetssætning
Beherske de klassiske sætninger af Turan, Brooks, Dirac, Smith
og Vizing.
Anvende algebraiske metoder illustreret ved det kromatiske
polynomium
Anvende liste-farvningsmetoden
Forstå implikationerne af stor minimumvalens
Kursusindhold:
1.Frembringerfunktioner, Catalan-tallene.
2.Tutte’s 1-faktorsætning. Petersen’s sætning.
3.Sætningerne af Ramsey og Turan.
4.Jordan’s kurvesætning.
5.Kuratowski’s sætning om plane grafer.
6.Hamilton kredse. Dirac’s sætning og Grinberg-kriteriet.
7.Antal hamilton kredse (Smith’s sætning) samt kromatisk tal og
maksimalvalens (Brooks’ sætning).
8.Vizing’s sætning om kantfarvning.
9.Kromatisk polynomium.
10.Liste-farvning. 5-farvning af plane grafer.
11.Grafer med stort kromatisk tal og ingen små kredse.
12.Mader’s resultater om implikation af stor minimumvalens.
