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 og Vizing.
• Anvende algebraiske metoder illustreret ved det kromatiske polynomium
• Anvende liste-farvningsmetoden
• Forstå implikationerne af stor minimumvalens

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.

01227/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.