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.
Sidst opdateret
23. maj, 2018
