308-760B 189-762B Graph Theory - Winter `06

Course Info

Time & Place:

Lectures Held Monday. Wednesday and Friday 10:00-11:30 in MC320. Three lectures a week until the study break. Then students will begin work on their project, so there will be no lectures for four weeks. The last two weeks of term we will have student presentations.

Instructor:

Bruce Reed MC301, breed@cs.mcgill.ca

Office Hours: Monday 11:30-1 or by appointment

Teaching Assistant:

None

Prerequisite: 308-362 or 189-552 and an undergraduate course on probability or permission of the instructor

Course Outline

List of Lecture Topics

Write up on f-factors

A Paper on the History of Skew Cutsets

List of Project Topics

Assessment

Assignments 20%, Final (to be held Wednesday March 1st) 40%, Written Project 40%: 10% lecture plan due March 15th (electronically), 15% lecture, 15% writeup due April 12th.

References

Text: Graph Theory 1736 to 1936, Biggs, Lloyd, and Wilson; Calendon Press, Oxford. 1998 Paperback edition.

Other references: The lecturer's books, Graph Colouring and the Probabilistic Method , Perfect Graphs and his unpublished manuscript: Rooted Routing Via Graph Minors.

Assignments

Assignment 1 (due Wednesday January 11th)

Assignment 2 (due Friday January 20th)

Assignment 3 (due Friday January 27th)

Assignment 4 (due Friday February 3rd)

Assignment 5 (due Friday February 10th)

Assignment 6 (due Friday February 17th)

Assignment Solutions

Solutions to Assignment 1

Solutions to Assignment 2

Solutions to later assignments can be found on the webpage of Louigi cgm.cs.mcgill.ca/(tilde)laddar/760.