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 grafet: 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.
