Videregående grafteori

• 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.

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.

01227

To timers forelæsning efterfulgt af to timers grupperegning

Minimum 6, Maksimum: 100.

Vær opmærksom på, at dette enkeltfagskursus har et minimumskrav til antal deltagere. Derudover er der begrænsning på antallet af studiepladser. Er der for få tilmeldinger oprettes kurset ikke. Er der for mange tilmeldinger, vil der blive trukket lod om pladserne. Du får besked om, om du har fået tildelt en studieplads senest 8 dage før kursusstart.