Overordnede kursusmål
Kurset vil indeholde en række klassiske grafteoretiske resultater,
såsom sætningerne af Tutte, Ramsey, Turan, Kuratowski,
Brooks, Dirac, Smith, Vizing, Roy-Gallai, Camion og Robbins 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,
Vizing, Roy-Gallai, Camion og Robbins.
- Anvende liste-farvningsmetoden.
- Anvende algebraiske metoder illustreret ved det kromatiske
polynomium.
- Forstå den probabilistiske metode illustreret med grafer med
stort kromatisk tal og uden korte kredse.
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.Liste-farvning.
10.Kromatisk polynomium.
11.Orienterede grafer.
12.Grafer med stort kromatisk tal og ingen små kredse.
Sidst opdateret
23. juli, 2024
