MM10 Grafteori FALL 2006 (instructor Bjarne Toft)

MM10 NEWS NO. 11 (November 22, 2006)

Does the Petersen Graph have a Hamiltonian Cycle ?
Professor Jochen Harant is trying it out in his driveway (Ilmenau, Thüringen, Germany)

The lecture on Wednesday Nov. 22, 2-4 PM, deals with edge-colourings of graphs. A set of notes on edge-colourings and in particular Vizing's Theorem and Goldberg's Conjecture, will be distributed.

The exercises on Monday Nov. 27 will deal with:

Vis at omega(G) (størrelsen af en størst mulig komplet delgraf) er højst det kromatiske tal. Vis at en to-delt graf har kromatisk tal = omega. Vis at komplementet af en to-delt graf har kromatisk tal = omega.
Lad G være en multigraf bestående af en ulige kreds af længde n, hvor kredsens kanter kan være multiple. Vi vil kalde en saadan multigraf for en ring-graf. Vis at G's kant-kromatiske tal er lig med maximum af de to tal [maximum valensen Delta i G] og [2m/(n-1) rundet op til nærmeste hele tal (m er G's kanttal)]. Det kantkromatiske tal er det mindste antal farver i en farvning af kanterne, hvor to kanter med et fælles endepunkt altid skal have forskellige farver.
Take a look at some of the unsolved problems from Graph Coloring Problems (Chapter 12), Wiley 1995.

The lecture on Wednesday Nov. 29, 2-4 PM,      will deal with trees.
The lecture on Wednesday Dec. 6, 2-4 PM,         will deal with Chapter I in the Red Book.
The lecture on Wednesday Dec. 13, 2-4 PM,      will deal with Chapter II in the Red Book.
The lecture on Wednesday Dec. 20, 2-4 PM,       will deal with Chapter III in the Red Book.

Tilmeldte til eksamen: Jacob, Nicolai, Mia, Vagn, Thomas, Jens, Lasse, Kirsten, Per. (Annegrethe er IKKE tilmeldt på den officielle liste).