Math 581: Topics in Graph Theory

Course Information

Instructor: Tom Zaslavsky
Office: LN-2231
Office phone: Ext. 2201
E-mail: zaslav@math.binghamton.edu

Office Hours (no appointment needed at these times):

MWF: 2:20-3:20
MW: 11:00-12:00
Or, make an appointment.


Go to: class notes | course announcement.
Download:
Supplemental problems: PostScript or dvi.
Max-Flow Min-Cut and Menger's theorems: PostScript or dvi. (A preliminary and incomplete verson.)

News

All the exciting combinatorial visitors have come and gone. No more for this semester. Alas!

Homework Assignments

Homework Set I

Due Wed., 2/10.
Do all exercises in Ch. 1.
Write up Ch. 1, ## 3, 7, 10, 11, 13, and # 1.A5.

Homework Set II

Due Wed., 2/24.
Read Ch. 3.
Do all exercises in Ch. 2.
Write up Ch. 2, ## 2, 4, 7, 10, 11, 14, 15, and # 2.A6.

Homework Set III

Due Wed., 3/24.
Do all exercises in Ch. 3.
Read Ch. 4. Do exercises 1-8, 11 in Ch. 4.
Write up Ch. 3, ## 1, 4, 5 (there are easy and hard solutions), 10 for Cn and Wn, 11, 13, 18, and ## 3.A1-A2.
Write up Ch. 4, ## 1, 5, 6, and ## 4.A1-A6.

Homework Set IV

Read Ch. 5.
Due Wed., 4/14 (?): Exercises 4-7, 10 in Ch. 5.
Due Fri., 4/16 (or Mon., 4/19): Write up Ch. 5, ## (?).

Homework Set V

Read Ch. 6.
Due Wed., 4/21: Ch. 6, Exercises 8, 10, 17, 19.
Due Mon., 4/26: Write up Ch. 6, ## 1, 2, 4-7, 9, 13, 15, 20.
Also read Ch. 7.

Homework Set VI

Read Ch. 7.
Due Tues., 4/27: Work on the max-flow min-cut problems and bring your ideas to class.
Due Wed., 4/28 for discussion: Ch. 7, Exercises 1-4, 8, 16, 18
Due Friday, 4/30: Write up Ch. 7, Exercises 6, 7, 9, 11, 19

Homework Set VII

(Optional for most of you.) Read Ch. 8 by Monday.
We're skipping in Chapters 9 and 10 the details of the method used to prove the 4CT. You might want to read that on your own, especially after hearing Robertson's talk on April 22, but unfortunately we have no time to spend on it in class.


Textbook

Martin Aigner, Graph Theory: A Development from the 4-Color Problem. Supplements & corrections.


The Four Color Problem

A recent new proof by Robertson, Seymour, and Thomas, nicely described without great technical detail. (Robertson will be visiting us in April.)

How is it connected to South African flora? (Remotely.) Notes by a South African mathematician.


My home page.