MM10  Grafteori  FALL 2006 (instructor Bjarne Toft)

MM10 NEWS NO. 9 (November 8, 2006)

The Petersen graph drawn as a unit distance graph (all edges have the same length).
It is not known which graphs may be drawn as unit distance graphs.
Is there a graph which requires five colours in a vertex-colouring that may be drawn as a unit distance graph ??
(You will be famous if you can answer this!)

The lecture on Wednesday Nov. 8, 2-4 PM,  will deal with Hamiltoncycles in graphs (based on a handout:  Hamiltonian Cycles (20 pages). The handout includes section 4.2 from the book [Bondy & Murty : Graph Theory with Applications, MacMillan 1976] and two original papers by [Erdös & Chvátal 1972] and by [Bondy 1978]. 

The exercises on Monday Nov. 13, 10-12 AM, will deal with some of the problems from section 4.2 in [Bondy & Murty], for example 4.2.1, 4.2.2,  4.2.3, 4.2.5, 4.2.6 (difficult!), 4.2.7, 4.2.8, 4.2.9 and 4.2.12 in [Bondy & Murty]. We may also take up the proof of the Erdös-Chvátal condition for the existence of a H-cycle and its relation to Dirac's (and Ore's) Theorem (see the two papers  [Erdös & Chvátal 1972] and by [Bondy 1978].

The lecture on Wednesday Nov. 15, 2-4 PM,       will deal with vertex-colourings of graphs.
The lecture on Wednesday Nov. 22, 2-4 PM,       will deal with edge-colourings  of graphs.
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.